LeetCode 141. Linked List Cycle    原题链接    简单

作者： 作者的头像   yxc ,  2018-05-31 16:51:41 ,  所有人可见 ,  阅读 3755

8


3

题目描述

给定一个链表，判断是否存在环。

进一步：能否只使用额外 $O(1)$ 的空间？

算法

(链表，指针扫描) $O(n)$

用两个指针从头开始扫描，第一个指针每次走一步，第二个指针每次走两步。如果走到 null，说明不存在环；否则如果两个指针相遇，则说明存在环。

为什么呢？
假设链表存在环，则当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 $x$ 步。
由于第二个指针每次比第一个指针多走一步，所以第一个指针再走 $x$步，两个指针就相遇了。

时间复杂度分析：第一个指针在环上走不到一圈，所以第一个指针走的总步数小于链表总长度。而第二个指针走的路程是第一个指针的两倍，所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return 0;
        ListNode *first = head, *second = first->next;

        while (first && second)
        {
            if (first == second) return true;
            first = first->next;
            second = second->next;
            if (second) second = second->next;
        }

        return false;
    }
};

4 评论

用户头像
顾辰枫   2023-02-27 19:43      1    踩      回复

个人觉得更优雅的写法

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode* fast = head, *slow = head;

        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;

            if (fast == slow) return true;
        }

        return false;
    }
};
用户头像
小马云写代码   2023-09-12 15:40         踩      回复

雀氏优雅

用户头像
irrational   2022-03-09 21:49      1    踩      回复

假设链表存在环，则当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 x 步。
由于第二个指针每次比第一个指针多走一步，所以第一个指针再走 x步，两个指针就相遇了。
记住了！

用户头像
你的喜帖是我的请帖   2023-10-12 14:17         踩      回复 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto l = head, r = head;
        while (l && r) {
            l = l->next;
            if (r = r->next)    r = r->next;
            else                return false;
            if (l == r)         return true;
        }
        return false;
    }
};