FXTi's blog
0%

linked-list-cycle

Posted on Edited on

Linked List Cycle – LeetCode 141

Problem

Description

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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) {
        unordered_set<ListNode*> s;
        while(head){
            if(s.find(head) != s.cend())
                return true;
            s.insert(head);
            head = head->next;
        }
        return false;
    }
};

思路

简单使用Set存储遍历过的指针。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$12$ ms，排名$74.71\%$

Better

思路

快慢双指针法，让慢的指针步进为一，快的指针步进为二，一同开始遍历链表，因为速度差为一，故可正常竞速，一旦快指针赶上了慢指针则确认成环。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$9$ ms，排名$67.64\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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) return false;
        ListNode *slow = head->next;
        ListNode *quick = head->next? head->next->next: nullptr;
        while(quick){
            if(slow == quick)
                return true;
            slow = slow->next;
            quick = quick->next? quick->next->next: nullptr;
        }
        return false;
    }
};