單鏈表反轉是數據結構與算法中的經典問題，它不僅考察對鏈表結構的理解，也考驗編程思維和技巧。本文將帶你從基礎實現到高級應用，全面掌握單鏈表反轉。

1. 理解單鏈表

在深入反轉算法之前，我們先回顧單鏈表的基本結構：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

單鏈表的特點是每個節點包含數據和指向下一個節點的指針，只能單向遍歷。

2. 基礎反轉方法

2.1 迭代法（最常用）

核心思想：逐個改變節點指向，從前往後反轉。

def reverse_list_iterative(head):
    prev = None
    current = head
    
    while current:
        # 保存下一個節點
        next_temp = current.next
        # 反轉指針
        current.next = prev
        # 移動指針
        prev = current
        current = next_temp
    
    return prev  # 新的頭節點

執行過程可視化：

原鏈表: 1 → 2 → 3 → 4 → 5 → None

步驟1: None ← 1  2 → 3 → 4 → 5 → None
步驟2: None ← 1 ← 2  3 → 4 → 5 → None
步驟3: None ← 1 ← 2 ← 3  4 → 5 → None
...
結果: None ← 1 ← 2 ← 3 ← 4 ← 5

2.2 遞歸法

核心思想：通過遞歸到達鏈表末端，然後從後往前反轉。

def reverse_list_recursive(head):
    # 遞歸終止條件
    if not head or not head.next:
        return head
    
    # 遞歸到最後一個節點
    new_head = reverse_list_recursive(head.next)
    
    # 反轉指針
    head.next.next = head
    head.next = None
    
    return new_head

遞歸過程分析：

reverse(1)
  reverse(2)
    reverse(3)
      reverse(4)
        reverse(5) → 返回5
      5.next = 4, 4.next = None
    5.next = 3, 3.next = None
  5.next = 2, 2.next = None
5.next = 1, 1.next = None

3. 進階反轉技巧

3.1 反轉部分鏈表

反轉鏈表中從位置 m 到 n 的部分：

def reverse_between(head, m, n):
    if not head or m == n:
        return head
    
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    # 移動到第m-1個節點
    for _ in range(m - 1):
        prev = prev.next
    
    # 開始反轉
    current = prev.next
    for _ in range(n - m):
        temp = current.next
        current.next = temp.next
        temp.next = prev.next
        prev.next = temp
    
    return dummy.next

3.2 K個一組反轉鏈表

每 k 個節點一組進行反轉，不足 k 的保持原樣：

def reverse_k_group(head, k):
    def reverse_sublist(start, end):
        prev, curr = None, start
        while curr != end:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev
    
    # 檢查是否有k個節點
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next
    
    # 反轉前k個節點
    new_head = reverse_sublist(head, node)
    # 遞歸處理剩餘部分
    head.next = reverse_k_group(node, k)
    
    return new_head

3.3 交替反轉

第一個k個節點反轉，下一個k個節點保持，如此交替：

def reverse_alternate_k_nodes(head, k):
    if not head or k <= 1:
        return head
    
    current = head
    prev = None
    reverse = True
    
    while current:
        if reverse:
            # 反轉k個節點
            section_start = current
            section_prev = None
            count = 0
            
            # 檢查是否有足夠的節點
            temp = current
            for _ in range(k):
                if not temp:
                    break
                temp = temp.next
            
            # 反轉當前段
            while current and count < k:
                next_temp = current.next
                current.next = section_prev
                section_prev = current
                current = next_temp
                count += 1
            
            # 連接已反轉部分
            if prev:
                prev.next = section_prev
            else:
                head = section_prev
            
            section_start.next = current
            prev = section_start
            reverse = False
        else:
            # 跳過k個節點
            count = 0
            while current and count < k:
                prev = current
                current = current.next
                count += 1
            reverse = True
    
    return head

4. 特殊場景反轉

4.1 反轉鏈表的前N個節點

def reverse_first_n(head, n):
    successor = None
    
    def reverse_n(node, count):
        nonlocal successor
        if count == 1:
            successor = node.next
            return node
        
        last = reverse_n(node.next, count - 1)
        node.next.next = node
        node.next = successor
        return last
    
    return reverse_n(head, n)

4.2 從末尾開始反轉

def reverse_from_end(head, k):
    # 先找到總長度
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # 轉換為從頭開始的位置
    m = length - k + 1
    return reverse_between(head, m, length)

5. 性能分析與比較

方法	時間複雜度	空間複雜度	適用場景
迭代法	O(n)	O(1)	通用，最常用
遞歸法	O(n)	O(n)	代碼簡潔，棧深度受限
部分反轉	O(n)	O(1)	局部操作
K組反轉	O(n)	O(n/k)	批量處理

6. 實戰技巧與注意事項

6.1 邊界情況處理

• 空鏈表
• 單節點鏈表
• 反轉位置超出範圍
• k值大於鏈表長度

6.2 調試技巧

def print_list(head):
    """打印鏈表用於調試"""
    result = []
    current = head
    while current:
        result.append(str(current.val))
        current = current.next
    print(" → ".join(result) + " → None")

6.3 常見錯誤

1. 忘記處理頭節點的更新
2. 指針丟失（在改變next前未保存）
3. 循環鏈表的形成
4. 邊界條件處理不完整

7. 綜合練習

題目：給定鏈表 1→2→3→4→5→6→7，要求實現：

1. 完全反轉
2. 反轉2-5位置
3. 每3個一組反轉
4. 交替每2個節點反轉

# 測試用例
def create_sample_list():
    nodes = [ListNode(i) for i in range(1, 8)]
    for i in range(len(nodes)-1):
        nodes[i].next = nodes[i+1]
    return nodes[0]

# 測試各種反轉方法
head = create_sample_list()
print("原鏈表:")
print_list(head)

print("\n完全反轉:")
print_list(reverse_list_iterative(create_sample_list()))

print("\n反轉位置2-5:")
print_list(reverse_between(create_sample_list(), 2, 5))

print("\n每3個一組反轉:")
print_list(reverse_k_group(create_sample_list(), 3))

總結

單鏈表反轉是算法學習中的重要里程碑。掌握從基礎到進階的各種反轉技巧，不僅能夠解決鏈表相關問題，更能培養嚴謹的編程思維和指針操作能力。建議通過大量練習來熟練掌握這些技巧，並理解每種方法適用的場景。

記住：多畫圖理解指針變化，多寫代碼加深印象，這是掌握鏈表問題的關鍵！