一、雙指針技術分類
1. 同速雙指針（同向移動）
- 特點：兩個指針以相同速度移動
- 適用場景：
- 鏈表逆序
- 查找倒數第 k 個元素
- 刪除倒數第 n 個節點
2. 快慢雙指針（異速移動）
- 特點：一個指針每次移動 1 步，另一個移動 2 步
- 適用場景：
- 檢測鏈表環存在性
- 計算環入口和長度
- 尋找中間節點
二、典型應用與算法實現
2.1 鏈表逆序
方法一：迭代法（同速雙指針）
python
def reverseList(head):prev = Nonecurr = headwhile curr:next_node = curr.next # 保存后續節點curr.next = prev # 反轉指針方向prev = curr # 雙指針同步移動curr = next_nodereturn prev # prev最終指向新頭節點
- 復雜度：O (n) 時間，O (1) 空間
方法二：遞歸法
python
def reverseList(head):if not head or not head.next:return headnew_head = reverseList(head.next)head.next.next = headhead.next = Nonereturn new_head
- 復雜度：O (n) 時間，O (n) 空間（遞歸棧）
2.2 查找倒數第 k 個元素
python
def findKthFromEnd(head, k):slow = fast = head# 快指針先走k步for _ in range(k):fast = fast.next# 雙指針同步移動while fast:slow = slow.nextfast = fast.nextreturn slow.val
- 關鍵點：快慢指針間距保持 k，當快指針到達末尾時，慢指針指向目標節點
2.3 刪除倒數第 n 個節點
python
def removeNthFromEnd(head, n):dummy = ListNode(0, head)first = dummysecond = dummy# 快指針先走n+1步for _ in range(n+1):first = first.next# 同步移動直到快指針到達末尾while first:first = first.nextsecond = second.next# 刪除操作second.next = second.next.nextreturn dummy.next
- 技巧：使用虛擬頭節點避免處理頭節點刪除的邊界情況
2.4 檢測鏈表環存在性
python
def hasCycle(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False
- 原理：若存在環，快慢指針必然相遇
2.5 計算環入口和長度
python
def detectCycle(head):# 第一步：檢測是否存在環slow = fast = headhas_cycle = Falsewhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:has_cycle = Truebreakif not has_cycle:return None# 第二步：找到環入口ptr1 = headptr2 = slowwhile ptr1 != ptr2:ptr1 = ptr1.nextptr2 = ptr2.nextreturn ptr1def calculateCycleLength(head):# 先找到環內節點slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:break# 計算環長度count = 0while True:slow = slow.nextcount += 1if slow == fast:breakreturn count
三、算法復雜度對比
| 問題類型 | 雙指針方法 | 時間復雜度 | 空間復雜度 | 優勢 |
|---|---|---|---|---|
| 鏈表逆序 | 迭代 | O(n) | O(1) | 無棧溢出風險 |
| 查找倒數第 k 元素 | 快慢指針 | O(n) | O(1) | 僅需一次遍歷 |
| 刪除倒數第 n 節點 | 快慢指針 | O(n) | O(1) | 無需預先計算長度 |
| 檢測環存在性 | 快慢指針 | O(n) | O(1) | 最優解法 |
| 環入口定位 | 雙指針定位 | O(n) | O(1) | Floyd 判圈算法變種 |
四、優化建議與應用場景
1. 優化技巧
- 虛擬頭節點：處理頭節點刪除時，避免復雜的邊界判斷
- 指針間距控制：通過調整快慢指針的初始間距，解決不同問題
- 兩次遍歷：在檢測環問題中，先用快慢指針檢測環，再用同速指針定位入口
2. 典型應用場景
- 鏈表操作：LeetCode 206（反轉鏈表）、19（刪除倒數第 N 個節點）
- 環檢測：LeetCode 141（環形鏈表）、142（環形鏈表 II）
- 數組問題：雙指針法解決兩數之和、三數之和等問題
