[面试题] Java链表操作：LeetCode 面试题 02.04 分割列表的解法与实现要点

本文将解析 LeetCode 面试题 02.04「分割列表」的解题思路，并重点阐述其 Java 实现中的关键细节与常见错误。题目要求：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

首先，我们来看一下这道题的核心解法图示与代码实现。

思路解析

解决此问题的经典方法是使用双链表法。我们可以创建两个带有「傀儡节点」(Dummy Node) 的链表：

1. 小链表 (SmallList)：用于链接所有值小于 x 的节点。
2. 大链表 (LargeList)：用于链接所有值大于或等于 x 的节点。

遍历原链表，根据节点值与 x 的比较，将节点分别尾插到对应的链表中。遍历结束后，将小链表的尾部与大链表的头部相连，并最终返回小链表的头节点（即其傀儡节点的下一个节点）。熟练掌握这类链表操作是提升算法解题能力的关键。

代码实现细节与易错点

以下是该算法的完整 Java 实现代码截图与文本。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 1. 创建两个带傀儡节点的大小链表
        ListNode smallDummy = new ListNode(0);
        ListNode largeDummy = new ListNode(0);
        ListNode smallTail = smallDummy;
        ListNode largeTail = largeDummy;

        // 2. 遍历原链表，进行分割
        while (head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = smallTail.next;
            } else {
                largeTail.next = head;
                largeTail = largeTail.next;
            }
            head = head.next;
        }

        // 3. 拼接大小链表
        smallTail.next = largeDummy.next;
        // 4. 关键步骤：将大链表尾部手动指向null
        largeTail.next = null;

        // 5. 返回新链表的头节点
        return smallDummy.next;
    }
}

在实现过程中，有三个细节需要特别注意，它们直接关系到程序的正确性：

1. 傀儡节点的创建与使用：为小链表和大链表分别创建傀儡节点 smallDummy 和 largeDummy，可以避免处理头节点为空的边界情况，简化代码逻辑。其对应的尾指针 smallTail 和 largeTail 初始时也指向各自的傀儡节点。

2. 尾插操作与尾指针更新：在遍历过程中，将符合条件的节点连接到对应链表的尾部（即 smallTail.next 或 largeTail.next），连接完成后，必须立即将对应链表的尾指针向后移动一位（smallTail = smallTail.next），以保证尾指针始终指向当前链表的最后一个节点。这是Java中处理链表增删操作的通用技巧。

3. 手动设置大链表尾部.next为null：这是最易被忽略的关键一步。原链表中的节点可能原本指向一个大于等于 x 的节点，但在拼接后，这个节点成为了大链表的尾节点。如果不将其 next 显式设置为 null，它可能依然指向原链表中的某个节点，从而导致新生成的链表出现环。因此，在拼接后执行 largeTail.next = null; 是必不可少的。

掌握以上要点，你就能稳健地解决这道链表分割问题。此思路同样可以迁移到其他需要对链表进行条件重排的场景中，例如，使用Python实现时，逻辑也是完全一致的。