双指针 6 （相交链表 leetcode 160）
2023-02-01 本文已影响0人
Sisyphus235
思想
双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。
实例
相交链表 leetcode 160
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
输入：
（1）headA: ListNode，一个链表
（2）headB: ListNode，另一个链表
输出：
ListNode，如果链表中无相交节点返回 None，有则返回相交的起始节点。
输入的两个链表 A 和 B 无环
举例：
当 headA = [4,1,8,4,5], headB = [5,6,1,8,4,5]，其中 [8,4,5] 共用时，返回环相交的起始节点 8。
关键点
核心是要设计一个方案让从 headA 和 headB 开始的指针能在相交节点相遇。
两个起点的长度不同，天然的结构是无法实现的，利用无环的特性，如果让两个起点在遍历自身链表结束后从对方的起始开始遍历，这样如果两条链表有相交节点就会出现在起始节点相遇的情况，无相交时会遍历完全部节点。
（1）有相交节点
headA ---\
meet --- end
headB ------ /
两个指针 pA 和 pB 分别从 headA 和 headB 开始遍历，分别走到 end 时交换彼此的开头。
当第一次 pA = pB 时，节点是 meet。
（2）无相交节点
headA --- endA
headB ------- endB
两个指针 pA 和 pB 分别从 headA 和 headB 开始遍历，分别走到 end 时交换彼此的开头。
pA 和 pB 同时走到终点，没有过相遇，此时返回 None。
编码
from typing import Optional
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def intersection_of_two_linked_lists(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
# 初始化
pA = headA
switchA = False
pB = headB
switchB = False
# 遍历寻找相交起始节点
while switchA is False or switchB is False or (pA is not None and pB is not None):
# 任何时候 pA 等于 pB 即是起始相交节点
if pA == pB:
return pA
# pA 遍历 headA 后遍历 headB
if pA is None:
pA = headB
switchA = True
else:
pA = pA.next
# pB 遍历 headB 后遍历 headA
if pB is None:
pB = headA
switchB = True
else:
pB = pB.next
