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相遇的。


没入环之前走了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号·苏公网安备 32059002001895号