思想
雙指針?biāo)惴ú粌H應(yīng)用于鏈表，在數(shù)組等數(shù)據(jù)結(jié)構(gòu)中也有廣泛應(yīng)用。
核心思路是指向問(wèn)題中的關(guān)鍵節(jié)點(diǎn)，根據(jù)問(wèn)題的上下文邏輯變換位置，最終解決問(wèn)題。
實(shí)例
相交鏈表 leetcode 160
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
輸入：
（1）headA: ListNode，一個(gè)鏈表
（2）headB: ListNode，另一個(gè)鏈表
輸出：
ListNode，如果鏈表中無(wú)相交節(jié)點(diǎn)返回 None，有則返回相交的起始節(jié)點(diǎn)。
輸入的兩個(gè)鏈表 A 和 B 無(wú)環(huán)
舉例：
當(dāng) headA = [4,1,8,4,5], headB = [5,6,1,8,4,5]，其中 [8,4,5] 共用時(shí)，返回環(huán)相交的起始節(jié)點(diǎn) 8。
關(guān)鍵點(diǎn)
核心是要設(shè)計(jì)一個(gè)方案讓從 headA 和 headB 開(kāi)始的指針能在相交節(jié)點(diǎn)相遇。
兩個(gè)起點(diǎn)的長(zhǎng)度不同，天然的結(jié)構(gòu)是無(wú)法實(shí)現(xiàn)的，利用無(wú)環(huán)的特性，如果讓兩個(gè)起點(diǎn)在遍歷自身鏈表結(jié)束后從對(duì)方的起始開(kāi)始遍歷，這樣如果兩條鏈表有相交節(jié)點(diǎn)就會(huì)出現(xiàn)在起始節(jié)點(diǎn)相遇的情況，無(wú)相交時(shí)會(huì)遍歷完全部節(jié)點(diǎn)。
（1）有相交節(jié)點(diǎn)
headA ---\
meet --- end
headB ------ /
兩個(gè)指針 pA 和 pB 分別從 headA 和 headB 開(kāi)始遍歷，分別走到 end 時(shí)交換彼此的開(kāi)頭。
當(dāng)?shù)谝淮?pA = pB 時(shí)，節(jié)點(diǎn)是 meet。
（2）無(wú)相交節(jié)點(diǎn)
headA --- endA
headB ------- endB
兩個(gè)指針 pA 和 pB 分別從 headA 和 headB 開(kāi)始遍歷，分別走到 end 時(shí)交換彼此的開(kāi)頭。
pA 和 pB 同時(shí)走到終點(diǎn)，沒(méi)有過(guò)相遇，此時(shí)返回 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
# 遍歷尋找相交起始節(jié)點(diǎn)
while switchA is False or switchB is False or (pA is not None and pB is not None):
# 任何時(shí)候 pA 等于 pB 即是起始相交節(jié)點(diǎn)
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
