Linked List - Linked List Cycle II

by LauCyun Sep 22,2014 15:30:42 5,108 views

Question

Problem Statement

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

Example

Given1->2->3->4->5->6, tail connects to node index 2, return 3.

题解 - 快慢指针

这题 Linked List - Linked List Cycle 的升级版,首先假设组成环的节点个数为\(r\),链表中节点个数为\(n\)

首先我们来分析下在链表有环时都能推出哪些特性:

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

从以上两个特性可知,在仅仅知道第一次相遇时的节点还不够,相遇后如果不改变既有策略则必然找不到环的入口。

接下来我们分析如何从第一次相遇的节点走到环的入口节点。还是先从实际例子出发,以下图为例:

slowfast节点分别初始化为节点12,假设快慢指针第一次相遇的节点为\( C_i\),那么此时慢指针正好走了\(n-r+i-1\)步,快指针则走了\(2(n-r+i-1)\)步,快慢指针第一次相遇时慢指针肯定没有走完整个环,且慢指针走的步数即为整数个环节点个数,由性质1和性质2可联合推出:

\((n-r+i-1)+1=x \cdot r\)  (\(x\)为非负整数)      式1

为什么在后面加1?是因为快指针初始化时多走了一步

现在分析下相遇的节点和环的入口节点之间的关联,要从环中第i个节点走到环的入口节点,则按照顺时针方向移动的节点数:

\(x \cdot r - i+1\)    (\(x\)为非负整数)             式2

由式1可以推知:\(n-r=x \cdot r-i\),也就是说从头节点走到环的入口节点所走的步数\(n-r\)

如果快慢指针第一次相遇时让快指针从头节点出发,慢指针仍从当前位置迭代,为了让快慢指针在环的入口点相遇,由式1和式2可以推知:需要让慢指针先走一步,否则会出现死循环。

C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * @param head: The first node of linked list.
 * @return: The node where the cycle begins.
 *          if there is no cycle, return null
 */
struct ListNode *detectCycle(struct ListNode *head) {
    if (NULL == head || NULL == head->next) {
        return NULL;
    }

    struct ListNode *slow = head, *fast = head->next;
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            slow = slow->next;
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

源码分析

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

复杂度分析

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

Reference

Tags