思想
雙指針?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í)例
刪除鏈表倒數(shù)第 N 個(gè)結(jié)點(diǎn) leetcode 19
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
輸入：
（1）head: ListNode，一個(gè)鏈表
（2）n: int，指定倒數(shù)第 n 個(gè)結(jié)點(diǎn)
輸出：
ListNode，將倒數(shù)第 n 個(gè)結(jié)點(diǎn)刪除，返回鏈表頭節(jié)點(diǎn)。
舉例：
當(dāng) head = [1,2,3,4,5], n = 2 時(shí)，刪除倒數(shù)第二個(gè)節(jié)點(diǎn) 4，返回 [1,2,3,5]。
關(guān)鍵點(diǎn)
核心是表達(dá)倒數(shù)第 n 個(gè)節(jié)點(diǎn)，這里的關(guān)鍵點(diǎn)是使用兩個(gè)指針，讓他們的差值是 n，當(dāng)后面的指針到達(dá)末尾的時(shí)候，前面的指針剛好是倒數(shù)第 n 個(gè)節(jié)點(diǎn)。
編碼
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_nth_node_from_end_of_list(head: ListNode, n: int) -> ListNode:
# 邊界條件
if n == 0:
return head
if n < 0:
raise RuntimeError('invalid n')
# 建立 dummy 節(jié)點(diǎn)，方便處理邊界條件
dummy = ListNode(next=head)
# 雙指針初始化
slow = fast = dummy
# 建立雙指針的差值
for _ in range(n):
if fast is None:
raise RuntimeError('nth node from end of list not exist')
fast = fast.next
# 定位倒數(shù)第 n 個(gè)節(jié)點(diǎn)
while fast.next is not None:
fast = fast.next
slow = slow.next
# 刪除該節(jié)點(diǎn)
slow.next = slow.next.next
return dummy.next
