本文共 1624 字，大约阅读时间需要 5 分钟。

题目描述

给定一个链表，如果是环形链表则返回开始入环的第一个节点，如果不是环形链表，则返回null。

如下图，节点3就是入环的第一个节点。

本题是在基础判定是否为上的升级，同样如果你用set集合，则非常简单，第一次重复添加时，直接返回即可。

解法

看一下如何不借助其他数据结构来实现。

首先还是先判断是否是环形链表，这个逻辑不变

第二次

第三次

第四次

第五次

第六次，相遇

之前判定是否为环形链表，到此就可以返回结果了，现在要返回节点3，此时我们只需要新建一个节点从头开始遍历，同时之前的慢节点继续遍历，当新节点与慢节点首次相遇时，就是入环节点。

新建一个节点，指向头节点

新节点、慢节点各走一步

再走一步，相遇

public class CycleNode_02 {
       public static void main(String[] args) {
           ListNode head = new ListNode(1);        ListNode n1 = new ListNode(2);        ListNode n2 = new ListNode(3);        ListNode n3 = new ListNode(4);        ListNode n4 = new ListNode(5);        ListNode n5 = new ListNode(6);        ListNode n6 = new ListNode(7);        head.next = n1;        n1.next = n2;        n2.next = n3;        n3.next = n4;        n4.next = n5;        n5.next = n6;        //环形链表n6下一节点又指回了n2        n6.next = n2;        CycleNode_02 c = new CycleNode_02();        System.out.println(c.findCycle(head));    }    public ListNode findCycle(ListNode head) {
           ListNode fast = head;        ListNode slow = head;        boolean hasCycle = false;        while (fast != null && fast.next != null) {
               fast = fast.next.next;            slow = slow.next;            if (fast == slow) {
                   hasCycle = true;                break;            }        }        //如果是环形链表，则从头和慢指针一起遍历，第一次相遇时，则是入环节点        if (hasCycle) {
               ListNode cur = head;            while (cur != slow) {
                   cur = cur.next;                slow = slow.next;            }            return cur;        } else {
               //如果不是环形链表，直接返回null            return null;        }    }}

转载地址：http://chlrb.baihongyu.com/