[Leetcode] 142. Linked List Cycle II (set / 快慢指针)
程序员文章站
2022-07-14 08:31:27
...
142. Linked List Cycle II (题目链接)
Medium
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
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.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.
Follow-up:
Can you solve it without using extra space?
方法1:使用set判重
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
d = set([])
node = head
while node:
if node in d:
return node
d.add(node)
node = node.next
return None
方法2:快慢指针
设置快指针是慢指针速度的两倍,从同一起点出发
设A点为起点,B点为开始出现环的点,C是相遇的点,推导如下
逆时针走:
AB=c, BC=b, CB= a
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow, fast = head, head
while fast:
slow = slow.next
fast = fast.next.next if fast.next else None
if slow == fast:
break
if slow == fast:
fast = head
while fast != slow:
slow = slow.next
fast = fast.next
return fast
else:
return None