LeetCode 86: 分隔链表

题目描述

给定一个单链表和一个整数 x，要求将链表分割成两部分，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。关键约束是必须保留原始链表中每个部分的相对顺序。

解题思路

这道题的核心在于'原地'重组链表而不破坏原有顺序。最稳妥的方法是使用两个虚拟头结点（dummy nodes），分别构建两条新链表：一条存放小于 x 的节点（smaller），另一条存放大于等于 x 的节点（bigger）。

遍历原链表时，根据节点值的大小，将其尾插到对应的子链表中。这样天然保证了相对顺序不变。遍历结束后，只需将 smaller 链表的尾部指向 bigger 链表的头部，并将 bigger 链表的尾部置空即可。

使用虚拟头结点的好处是可以避免处理头指针为空或需要修改头指针的特殊情况，让逻辑更统一。实际运行时，要注意断开 big 链表的尾部，防止形成环。

代码实现

C++ 版本

在 C++ 中需要注意内存管理，遍历完成后记得释放虚拟头结点，防止内存泄漏。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // 创建两个虚拟头结点，简化边界处理
        ListNode* bigger_dummy = new ListNode(-1);
        ListNode* bigger_point = bigger_dummy;
        ListNode* smaller_dummy = new ListNode(-1);
        ListNode* smaller_point = smaller_dummy;
        
        ListNode* cur = head;
        while (cur) {
            if (cur->val < x) {
                smaller_point->next = cur;
                smaller_point = smaller_point->next;
            } else {
                bigger_point->next = cur;
                bigger_point = bigger_point->next;
            }
            cur = cur->next;
        }
        
        // 连接两条链表
        smaller_point->next = bigger_dummy->next;
        // 断开 big 链表的尾部，防止形成环
        bigger_point->next = NULL;
        
        ListNode* retHead = smaller_dummy->next;
        delete smaller_dummy;
        delete bigger_dummy;
        return retHead;
    }
};

Java 版本