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
-1, then there is no cycle in the linked list.
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.
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Input: head = , pos = -1 Output: false Explanation: There is no cycle in the linked list.
Can you solve it using O(1) (i.e. constant) memory?
1. Two Pointers
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # Time: O(n) # Space: O(1) class Solution: def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False faster, slower = head, head while faster and slower: if faster.next: faster = faster.next.next else: faster = None slower = slower.next if faster == slower: return True return False # 17/17 cases passed (48 ms) # Your runtime beats 89.92 % of python3 submissions # Your memory usage beats 100 % of python3 submissions (16 MB)