Task

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example

  • Example 1:
1
2
3

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

leetcode141_1

  • Example 2:
1
2
3

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

leetcode141_2

  • Example 3:
1
2
3

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

leetcode141_3

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Solution

集合

  • 用集合存储每个节点的地址，每看到一个节点就查看它是否在集合中，若看到某个节点时它已在集合中，则有环
  • 时间复杂度：只需遍历一次，每次循环向unordered_set中插入元素的时间是O(1)，故总时间复杂度是O(n)
  • 空间复杂度：新建集合的元素数等于链表的节点数，O(n)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Runtime: 20 ms, faster than 18.58% of C++ online submissions for Linked List Cycle.
// Memory Usage: 9.9 MB, less than 43.42% of C++ online submissions for Linked List Cycle.
/**
 * 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 *> visit;
        while(head){
            //若该节点已被访问过，则有环
            if(visit.count(head)) return true;
            visit.insert(head);
            head=head->next;
        }
        return false;
    }
};

双指针

  • 使用一个快指针和一个慢指针：
    • 若无环，则快指针一定先走到尾部
    • 若有环，两指针一定会都进入环内，故快指针一定会再次追上满指针
  • 时间复杂度：只需遍历一次，或是快指针比慢指针多跑一圈，故O(n)
  • 空间复杂度：只用了两个指针，O(n)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Runtime: 8 ms, faster than 93.01% of C++ online submissions for Linked List Cycle.
Memory Usage: 7.7 MB, less than 100.00% of C++ online submissions for Linked List Cycle.
/**
 * 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) {
        ListNode *fast=head,*low=head;
        //由于快指针一次走两步，故需检查它和它的next
        while(fast && (fast->next)){
            //指针移动
            low=low->next;
            fast=fast->next->next;
            //相遇则有环
            if(fast==low) return true;
        }
        //走完还未相遇则无环
        return false;
    }
};