首页 > 代码库 > [LeetCode]Linked List Cycle

[LeetCode]Linked List Cycle

题目:Linked List Cycle

判断一个单链表中是否有环,要求常量空间复杂度;

思路:

使用两个指针同时从链表表头开始移动,一个移动一步,一个移动两步,直到两个指针重合或某一指针指向链尾。

两个指针重合则单链表有环存在,否则没有。

第二个指针以第一个指针的两倍的速度移动,而第一个指针每次移动一步,这样只要有环,两个指针必定能重合。

bool LeetCode::hasCycle(ListNode *head){
    if (!head)return false;
    ListNode *p = head, *q = head;
    while (q){
        p = p->next;//p每次前进一步
        if (!q->next)return false;//q是否到链尾
        q = q->next->next;//q每次前进两步
        if (p == q)return true;//重合则有环
    }
    return false;
}

题目:Linked List CycleII

如果一个单链表中有环,找到环的开始位置,没有则返回null;

要求常量空间复杂度;

思路:

使用两个指针同时从链表表头开始移动,一个移动一步,一个移动两步,直到两个指针重合或某一指针指向链尾。

如果两个指针重合,则跳出循环;

然后将其中一个指针重新指向链头,两个指针每次移动一步,知道再次重合,此时重合位置必定为环头。

证明:

假设某单链表有环,不妨设链头到链表环开始位置的长度设为a,链表环的长度设为b;则链表的长度为a+b;

先移动两指针直到第一次重合,

一次移动一步的指针移动的步数:n = a + l*b + c
一次移动两步的指针移动的步数:2n = a + k*b + c = 2(a + l*b + c)

a + k*b + c = 2(a + l*b + c) => a + c = (k - l)b

两个指针第一次相遇时,l = 0;

  可以用反证法证明:假设l = k0(k0不等于0)是第一次相遇时l的值,则a + c = (k - k0)*b;

  此时当l1 = 0,k1 = k - k0时,此时两个指针也会相遇,且l1 < l0,即l1是比l0还早的一次相遇,矛盾了。

于是l = 0,则a + c = k * b;

当前两个指针的位置为n = a + l*b + c = a + c(l = 0) = k * b;

此时将其中一个指针重新指向链头,然后两个指针每次移动一步,直到再次相遇;

此时,另一个指针沿着环移动到环头需要步数:k*b - c = a;(k >= 1)

所以,两个指针第二次重合必定在环的开头位置。

 

ListNode *LeetCode::detectCycle(ListNode *head){
    if (!head)return nullptr;
    bool hasCycle = false;
    ListNode *p = head, *q = head;
    while (q){
        p = p->next;//p每次前进一步
        if (!q->next)return nullptr;//q是否到链尾
        q = q->next->next;//q每次前进两步
        if (p == q){
            hasCycle = true;//重合则有环
            break;
        }
    }
    if (!hasCycle)return nullptr;
    p = head;//p再次从头直到与q重合,则当前位置为环的开始位置
    while (p != q){
        p = p->next;
        q = q->next;
    }
    return p;
}

 

[LeetCode]Linked List Cycle