双指针 5 （环形链表 II leetcode 142）
2023-01-31 本文已影响0人
Sisyphus235
思想
双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。
实例
环形链表 II leetcode 142
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
输入：
head: ListNode，一个链表
输出：
ListNode，如果链表中无环返回 None，有环则返回环的开始节点。
举例：
当 head = [3,2,0,-4], [2,0,-4] 成环时，返回环开始的节点 2。
关键点
核心是判断是否有环，并寻找到环开始的位置。
（1）判断环
使用两个指针，快的步长为 2，慢的步长为 1，当快的到达末端前，如果和慢的相遇，存在环。
（2）环开始的位置
head ----> start - \
/ meet
| |
\ /
- - -
slow 和 fast 分别从 head 出发，经过了环开始位置 start，在 meet 处相遇。
此时 slow 行进距离为 head -> start -> meet，fast 形近距离为 head -> start -> meet --[n 圈]--> meet。 设 head -> start = a
，start -> meet = b，环长度 c，fast 在相遇前饶了 n 圈。
slow 距离 = a + b，fast 距离 = a + b + nc。
fast 行进距离是 slow 的 2 倍，a + b + nc = 2(a + b) => a + b = nc => a = nc - b。
如果从 meet 和 head 用相同步速前进，当 head 处前进 a 到达 start 的时候，meet 处前进了 nc - b 也到达了 start，这样就找到了环的起始点。
编码
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def linked_list_cycle_ii(head: ListNode) -> ListNode:
# 初始位置都在 head
slow = fast = head
# fast 步速 2，slow 步速 1，判断是否有环
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
# 存在环，寻找环初始节点
if slow == fast:
start = head
while start != fast:
start = start.next
fast = fast.next
return start
return None
