leetcode142.环形链表2

leetcode142.环形链表2

二月 23, 2020

leetcode142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

我先说一下我自己的思路，先判断链表里面是否存在环，然后把环的长度length求出来，最后再从头开始遍历。如果当前节点加上length的值还是自己，就把环的入口找到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode detectCycle(ListNode head) {
       if(head==null||head.next==null)return null;
       ListNode i=head,j=head.next;
       while(j!=null&&j.next!=null&&j.next.next!=null){
           if(j==i)break;
           i=i.next;
           j=j.next.next;
       }
       if(j!=i)return null;
       int length=0;
       j=j.next;length++;
       while(i!=j){//求环的长度
           j=j.next;
           length++;
       }
       i=head;j=head;
       for(int k=0;k<length;k++){
           j=j.next;
       }
       while(i!=j){
           i=i.next;
           j=j.next;
       }
       return i;   
   }

看到评论区发现有一种更好的方法，在这里环形链表II。
这里摘抄出来。指针有两个速度fast和slow，而fast的速度是slow的二倍，fast走的路程是slow的两倍 –> f=2s。假设环之前的长度是a，环的长度是b，那么在相遇的时候 f=a+nb 。这两个式子可以得到 f=2nb, s=nb。
如果从头head，走到环的入口需要 a+nb 的长度。慢指针已经走了 nb 步，所以慢指针再走a步就会到达环的入口。所以只需要再找一个指针能走a步，并且到达环的入口就可以，这样的指针就是头指针。
leetcode 14/100