Linked List Cycle II

Question

  1. Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
  3. Example
  4. Given -21->10->4->5, tail connects to node index 1，return node 10
  6. Challenge
  7. Follow up:
  8. Can you solve it without using extra space?

题解 - 快慢指针

题 Linked List Cycle | Data Structure and Algorithm 的升级版，题目要求不适用额外空间，则必然还是使用快慢指针解决问题。首先设组成环的节点个数为 r, 链表中节点个数为 n. 首先我们来分析下在链表有环时都能推出哪些特性：

  1. 快慢指针第一次相遇时快指针比慢指针多走整数个环, 这个容易理解，相遇问题。
  2. 每次相遇都在同一个节点。第一次相遇至第二次相遇，快指针需要比慢指针多走一个环的节点个数，而快指针比慢指针多走的步数正好是慢指针自身移动的步数，故慢指针恰好走了一圈回到原点。

从以上两个容易得到的特性可知，在仅仅知道第一次相遇时的节点还不够，相遇后如果不改变既有策略则必然找不到环的入口。接下来我们分析下如何从第一次相遇的节点走到环的入口节点。还是让我们先从实际例子出发，以下图为例。

Linked List Cycle II

slow和fast节点分别初始化为节点1和2，假设快慢指针第一次相遇的节点为0, 对应于环中的第i个节点 C_i, 那么此时慢指针正好走了 n - r - 1 + i 步，快指针则走了 2 \cdot (n - r - 1 + i) 步，且存在[^1]: n - r - 1 + i + 1= l \cdot r. (之所以在i后面加1是因为快指针初始化时多走了一步) 快慢指针第一次相遇时慢指针肯定没有走完整个环，且慢指针走的步数即为整数个环节点个数，由性质1和性质2可联合推出。

现在分析下相遇的节点和环的入口节点之间的关联，要从环中第i个节点走到环的入口节点，则按照顺时针方向移动[^2]: (l \cdot r - i + 1) 个节点 (l 为某个非负整数) 即可到达。现在来看看式[^1]和式[^2]间的关系。由式[^1]可以推知 n - r = l \cdot r - i. 从头节点走到环的入口节点所走的步数可用 n - r 表示，故在快慢指针第一次相遇时让另一节点从头节点出发，慢指针仍从当前位置迭代，第二次相遇时的位置即为环的入口节点！

Note 由于此题快指针初始化为头节点的下一个节点，故分析起来稍微麻烦些，且在第一次相遇后需要让慢指针先走一步，否则会出现死循环。

对于该题来说，快慢指针都初始化为头节点会方便很多，故以下代码使用头节点对快慢指针进行初始化。

C++

  1. /**
  2.  * Definition of ListNode
  3.  * class ListNode {
  4.  * public:
  5.  *     int val;
  6.  *     ListNode *next;
  7.  *     ListNode(int val) {
  8.  *         this->val = val;
  9.  *         this->next = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param head: The first node of linked list.
  17.      * @return: The node where the cycle begins.
  18.      *           if there is no cycle, return null
  19.      */
  20.     ListNode *detectCycle(ListNode *head) {
  21.         if (NULL == head || NULL == head->next) {
  22.             return NULL;
  23.         }
  25.         ListNode *slow = head, *fast = head;
  26.         while (NULL != fast && NULL != fast->next) {
  27.             fast = fast->next->next;
  28.             slow = slow->next;
  29.             if (slow == fast) {
  30.                 fast = head;
  31.                 while (slow != fast) {
  32.                     fast = fast->next;
  33.                     slow = slow->next;
  34.                 }
  35.                 return slow;
  36.             }
  37.         }
  39.         return NULL;
  40.     }
  41. };

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     public ListNode detectCycle(ListNode head) {
  14.         if (head == null || head.next == null) {
  15.             return null;
  16.         }
  18.         ListNode slow = head;
  19.         ListNode fast = head;
  20.         while (fast.next != null && fast.next.next != null) {
  21.             slow = slow.next;
  22.             fast = fast.next.next;
  23.             if (slow == fast) {
  24.                 fast = head;
  25.                 while (fast != slow) {
  26.                     fast = fast.next;
  27.                     slow = slow.next;
  28.                 }
  29.                 return fast;
  30.             }
  31.         }
  32.         return null;
  33.     }
  34. }

源码分析

  1. 异常处理。
  2. 找第一次相遇的节点。
  3. 将fast置为头节点，并只走一步，直至快慢指针第二次相遇，返回慢指针所指的节点。

复杂度分析

第一次相遇的最坏时间复杂度为 O(n), 第二次相遇的最坏时间复杂度为 O(n). 故总的时间复杂度近似为 O(n), 空间复杂度 O(1).

Reference