鏈表逆序交替合併演算法深度解析與 Java 實現

前言

在資料結構與演算法的面試題中，鏈表操作佔據重要地位。本文將深入剖析一道經典題目：將兩條鏈表逆序後交替合併。給定兩條鏈表 A: 1→2→3→4 和 B: a→b→c→d，期望輸出為 4→d→3→c→2→b→1→a。我們將從問題建模、核心邏輯、邊界處理三個維度循序漸進講解，並提供完整的 Java 實現代碼。

問題建模與節點定義

首先定義單向鏈表節點結構，僅包含 next 指針：

class Node {
    public Node next;
    // 其他數據域省略
}

目標函數簽名為 Node reverse_merge(Node A, Node B)，傳入兩條鏈表頭節點，返回合併後的新頭節點。

核心思路：三階段指針重組

演算法將整個過程劃分為三個階段：預處理階段、主循環階段、收尾階段。關鍵在於維護三個關鍵指針——A（當前 A 鏈表節點）、nextA（A 的下一節點）、B（當前 B 鏈表節點），並輔以 nextB 暫存 B 的下一節點，防止斷鏈丟失節點。

1. 預處理：處理頭節點與特殊情況

若 A 僅有一個節點（A.next == null），直接將 A 指向 B 並返回。否則，執行首輪「原子操作」：斷開 B 首節點與其後繼，使 A 指向 B，並將 nextA、nextB 就位，為進入主循環做準備。此步解決了 B 鏈表首節點 a 需 next=null 的特殊性。

2. 主循環：原子操作的重複執行

循環條件為 nextA.next != null，即 A 還有後續節點。每輪循環完成一次「雙向穿針」：

• B.next = A：B 當前節點指向 A 當前節點
• A = nextA; nextA = A.next：A 推進到下一節點
• A.next = B：新 A 節點指向 B 當前節點
• B = nextB; nextB = B.next：B 推進到下一節點（此處 nextB 為上輪暫存）

此過程將兩條鏈表從尾部向頭部交替串聯，形成 ...→3→c→2→b 之類的局部有序片段。

3. 收尾：處理最後兩個節點

循環結束時，B 鏈表已到末尾（d 節點），A 仍剩最後一個節點（4）。需手動完成最後連接：nextB.next = A; nextA.next = B;，並返回 nextA 作為新頭節點（即原 A 的尾節點 4）。

完整 Java 實現代碼

Node reverse_merge(Node A, Node B) {
    // A 僅有一個節點
    if (A.next == null) {
        A.next = B;
        return A;
    }
    // A、B 均 ≥ 2 個節點
    Node nextA, nextB;
    nextB = B.next;
    B.next = null;        // 斷開 B 首節點後繼
    nextA = A.next;
    A.next = B;           // A 首節點指向 B 首節點
    B = nextB;            // B 推進
    while (nextA.next != null) {
        B.next = A;       // B 指向 A
        A = nextA;        // A 推進
        nextA = A.next;
        A.next = B;       // 新 A 指向 B
        B = nextB;        // B 推進
    }
    nextB.next = A;       // 收尾連接
    nextA.next = B;
    return nextA;         // 返回新頭節點
}

複雜度分析與局限性

• 時間複雜度：O(min(m, n))，m、n 為兩鏈表長度，單次遍歷即可完成。
• 空間複雜度：O(1)，原地操作，僅使用常數級額外指針。
• 已知局限：代碼假設兩鏈表等長；若長度不等，循環條件與收尾邏輯需額外判斷。另 Node 類未定義數據域，實際使用時需補全。

總結

本文通過「預處理→主循環→收尾」三階段拆解，詳細闡述了逆序交替合併兩條鏈表的指針操作邏輯。核心在於利用 nextB 暫存斷鏈節點，並在循環中維持三指針同步推進。掌握此模式，對解決各類鏈表重組問題（如 LRU 快取淘汰、多路歸併等）極具啟發意義。