LeetCode: Linked List Cycle I & II

Given a linked list, determine if it has a cycle in it.

想了好半天没想出来，后来看网上的做法。

用快慢两个指针，慢指针每次移动一位，快指针每次移动两位。如果存在环的话，两个指针一定会相遇。

最差的情况是，在慢指针进入环的时候，快指针恰巧在慢指针前面一位，如果环的长度为k<=n的话，这时需要n-1步，两个指针能再次相遇。O(n)。

加上慢指针进入环之前的时间O(n)。所以整个算法的时间复杂度为—O(n)。

 1 public boolean hasCycle(ListNode head) {
 2         ListNode slow = head, fast = head;
 3         
 4         while (true) {
 5             if (fast == null) return false;
 6             else if (fast.next == null) return false;
 7             else fast = fast.next.next;
 8             
 9             slow = slow.next;
10             if (slow == fast) return true;
11         }
12     }

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

又想了好半天，还是没想出来。看网上的一个很好。

在网上搜集了一下这个问题相关的一些问题，思路开阔了不少，总结如下：

1. 环的长度是多少？

2. 如何找到环中第一个节点（即Linked List Cycle II）？

3. 如何将有环的链表变成单链表（解除环）？

4. 如何判断两个单链表是否有交点？如何找到第一个相交的节点？

首先我们看下面这张图：

LeetCode: Linked List Cycle I & II

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

下面我们来挨个问题分析。

1. 方法一（网上都是这个答案）：

第一次相遇后，让slow,fast继续走，记录到下次相遇时循环了几次。因为当fast第二次到达Z点时，fast走了一圈，slow走了半圈，而当fast第三次到达Z点时，fast走了两圈，slow走了一圈，正好还在Z点相遇。

方法二：

第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。

方法三（最简单）：

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

2. 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

3. 在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

4. 如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

 1 public ListNode detectCycle(ListNode head) {
 2         ListNode first = head;
 3         ListNode slow = head, fast = head;
 4         while (true) {
 5             if (fast == null) return null;
 6             else if (fast.next == null) return null;
 7             else fast = fast.next.next;
 8         
 9             slow = slow.next;
10             if (fast == slow) break;
11         }
12         
13         while (first != slow) {
14             slow = slow.next;
15             first = first.next;
16         }
17         
18         return first;
19     }

LeetCode: Linked List Cycle I & II

相关推荐