Last Updated on 2022-03-09 by Clay
題目
Givenhead, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following thenextpointer. Internally,posis used to denote the index of the node that tail'snextpointer is connected to. Note thatposis not passed as a parameter. Returntrueif there is a cycle in the linked list. Otherwise, returnfalse.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range
[0, 104]. -105 <= Node.val <= 105posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
題目給定一組鏈結串列的資料，我們要判斷該 list 中是否存在著迴圈（cycle）。
解題思路
這題有兩種作法：
方法一、將所有走過的節點儲存起來，然後判斷我們是否又有到同樣的節點；如果存在著終點（null），則返回 false。
方法二、宣告兩個位於開頭 head 的節點，一個每次走一步、一個每次走兩步。如果走得快的跟走得慢的走到了同樣的節點，則證明串列中存在著迴圈；如果走得快的率先抵達了終點，則返回 false。
儲存走過的節點
儲存走過的節點複雜度
| Time complexity | O(n) |
| Space complexity | 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) {
// Init
unordered_map<ListNode*, bool> visited;
// Iteration
while (head != nullptr) {
visited[head] = true;
if (visited.count(head->next)) {
return true;
}
head = head->next;
}
return false;
}
};
儲存走過的節點 Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# Init
visited = []
# Iteration
while head:
if head in visited: return True
else: visited.append(head)
# Step
head = head.next
return False兩節點
這個方法才符合 follow-up 要做到的事情：只使用到 O(1) 的空間。
兩節點複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
兩節點 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) {
// Init
ListNode* slow = head;
ListNode* fast = head;
// Find
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
兩節點 Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# Init
slow = head;
fast = head;
# Find
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False