leetcode题解 problem 142 Linked List Cycle II

Tags:

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

Follow up:

Can you solve it without using extra space?

题意:

判断一个链表是否有环,有环的话返回环的起始节点,无环的话返回NULL。

题解:

Linked List Cycle的升级,不仅要判断有无环,还要求入口。很显然可以在Linked List Cycle的基础上来做。

这里我直接翻译ngcl的answer,写得非常好:

  1. 用slower和faster方法判断是否有环;
  2. 设链表的头节点是head,环的入口节点是entry,slower和faster2个指针相遇的节点是meeting;
  3. 设L1是head到entry的正向距离,L2是entry到meeting的正向距离,C是环的长度,n是faster指针在cycle里遍历的次数(不到一遍算0);

根据上面的定义,可知:

  1. 当slower和faster相遇时,slower已经走了L1 + L2的距离,也即head和meeting的距离;
  2. 当slower和faster相遇时,faster已经走了L1 + L2 + n * C的距离;
  3. 因为slower步进1,而faster步进2,那么当slower和faster第一次相遇时,faster已经走的距离是slower已经走的距离的两倍,即 2* (L1 + L2) = L1 + L2 + n * C => L1 = (n - 1) * C + (C - L2)

L1 = (n - 1) * C + (C - L2) 这个等式表明, head和entry的距离(L1),等于meeting到entry的正向距离(链表是有遍历方向的)。

这是因为式子中的 (n - 1) * C相当于走n-1个循环,对一个指向meeting的环内指针来说,走(n - 1) * C等于回到起点,所以式子可以简化成 L1 = C - L2

画成图是这样子:

1.png

ngcl的代码如下:

 1   ListNode *detectCycle(ListNode *head) {
 2      if (head == NULL || head->next == NULL)
 3          return NULL;
 4  
 5      ListNode *slow  = head;
 6      ListNode *fast  = head;
 7      ListNode *entry = head;
 8  
 9      while (fast->next && fast->next->next) {
10          slow = slow->next;
11          fast = fast->next->next;
12          if (slow == fast) {                      // there is a cycle
13              while(slow != entry) {               // found the entry location
14                  slow  = slow->next;
15                  entry = entry->next;
16              }
17              return entry;
18          }
19      }
20      return NULL;                                 // there has no cycle
21  }
(未经授权禁止转载)
Written on July 8, 2015

博主将十分感谢对本文章的任意金额的打赏^_^