142. Linked List Cycle II
in LeetCode with 0 comment

142. Linked List Cycle II

in LeetCode with 0 comment
题目链接: https://leetcode.com/problems/linked-list-cycle-ii/description/

题目

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

分析

这道题知乎面试的时候问到了,当时比较蠢,以为这个问题很复杂....

现在回头来看其实非常简单,p1是慢指针,p2是快指针。

p1每次走一步,p2每次走两步

如果有环的话,那么p1迟早会和p2相遇的。


假定:相遇的时候,p1已经走了k步,那p2就已经走了2k步

没入环之前走了a步

p1肯定是第一环都没走完(假定已经走了m步吧)

p2已经走了 r(环长) + m 只能是一圈,这里可以想想


p1 -> a + m = k
p2 -> a + r +m = 2k

-> a = r - m

所以从起点开始到 入环点的距离,跟相遇点到入环点的距离相同。

class Solution {
public:

ListNode *detectCycle(ListNode *head) {
    if (head == NULL || head->next == NULL)
        return NULL;
    // 快慢指针
    ListNode *p1 = head->next, *p2 = head->next->next, *p3 = head;
    // 默认无环
    int flag = 0;
    // 若不是环,那么p2会指向NULL
    while (p2&&p1&&p2->next) {
        if (p2 != p1) {
            p2 = p2->next->next;
            p1 = p1->next;
        }
        else {
            flag = 1;
            break;
        }
    }
    if (flag == 0) {
        return NULL;
    }
    else {
        while (p1 != p3) {
            p1 = p1->next;
            p3 = p3->next;
        }
        return p3;
    }
}

};

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号