142. Linked List Cycle II

题目描述

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

<b>Note: Do not modify the linked list.</b>

Follow up:

Can you solve it without using extra space?

解题思路

无视Follow up中的内容的话，很容易就能想到，用一个长度为N的数组存已经经过的节点，然后每次访问下一个元素时，先在数组中查找是否访问过这个元素，若没有，放入数组，并继续访问下一个元素；若有，则返回这个元素。如果下一个元素为空，则返回空值。这样做我们不难发现，经过第k个元素时，需要查找k-1个元素，也就是说，时间复杂度是的规模，而且，数组开辟的额外空间是O(N)的规模。显然这不是一个好方法。

那么我们要如何改善它呢？数组的查找显然是耗费时间非常多的，因此，如果我们把查找时间降低到O(1)的规模，那么，整个算法的复杂度规模就可以显著下降了。查找时间为O(1)的数据结构，我们马上就能想到哈希表也就是对应c++中的map类型。经过这一轮优化，我们不难发现，时间复杂度已经下降到了O(N)的规模。

然而，题目要求的不可开辟O(N)复杂度的额外空间要怎么解决呢？要解决这个问题的核心在于，我们如何确定链表有环，即什么时候再次经过我们访问过的元素。如果单纯的用一个指针来遍历整个链表的话，我们是很难得知是否访问过这个元素的，要确定这个就必须要开辟空间存储访问过的元素。但这时，聪明的discussion中的老哥们想到，如果有两个不一样快的指针，同时在遍历这个链表，若它有环存在，快的指针就必定能在后面追上慢的指针；反之，则环不存在。

既然确定环的问题解决了，我们又要如何确定环开始的节点呢？假设两个指针，快的指针在每次迭代中走两步，慢的指针在每次迭代中走一步。当快的指针追上慢的指针时，快的指针比慢的指针走的路程要多一倍。先证明：快的指针会在慢指针到达终点前与它相遇：

k为环的长度，s为起点到循环开始的长度，慢指针走了t次后到达终点。
慢指针走的路程 = s + k
快指针走的路程 = 2(s + k) = s + k + k + s
显然，快指针已经超过了慢指针。因此它们一定会在慢指针走到终点前相遇。并且快指针超过了慢指针s的长度。

也就是说，当它们相遇时，快指针比慢指针多走了kr的长度，假如这时，快指针的速度变得跟慢指针一样，并且从链表头开始走会怎么样呢？

由于速度相同，它们之间的路程差不会再拉开，一直维持在kr。这时候，让慢指针和速度跟它一致的快指针一起开始走，当慢指针走到终点并回到循环开始元素时，快指针由于刚好快它k倍数的长度，就会在循环开始元素二者相遇。这时候，我们把它们相遇的元素返回即可。

时间复杂度分析

慢指针刚好跑完整个链表，总时间复杂度为O(N)。

空间复杂度分析

两个指针复杂度O(1)

源码

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL)
      return NULL;
    ListNode* p = head;
    ListNode* q = head;
    bool cycle = false;
    while (p != NULL && q != NULL) {
      p = p->next;
      if (q->next == NULL)
        return NULL;
      else {
        q = q->next->next;
      }
      if (p == q) {
        cycle = true;
        break;
      }
    }
    if (!cycle)
      return NULL;
    p = head;
    while (p != q) {
      p = p->next;
      q = q->next;
    }
    return p;
  }
};