两段链表分区代码的差异及输出不同的原因解析

问题背景 #

给定链表的头节点head和值x，对链表进行分区，需满足：

• 所有值小于x的节点位于大于或等于x的节点之前
• 保留两个分区内节点的原始相对顺序

正确代码实现 #

ListNode* partition(ListNode* head, int x) {
    ListNode* small = new ListNode(-1);
    ListNode* large = new ListNode(-1);
    ListNode* smallhead = small;
    ListNode* largehead = large;

    while(head) {
        if(head->val<x) {
            small->next = head;
            small = small->next;
            head = head->next;
            small->next = NULL;
        }
        else {
            large->next = head;
            large = large->next;
            head = head->next;
            large->next = NULL;
        }
    }
    small->next = largehead->next;

    return smallhead->next;
}

错误代码实现 #

ListNode* partition(ListNode* head, int x) {
    ListNode* small = new ListNode(-1);
    ListNode* large = new ListNode(-1);
    ListNode* smallhead = small;
    ListNode* largehead = large;

    while(head) {
        if(head->val<x) {
            small->next = head;
            small = small->next;
            small->next = NULL;
            head = head->next;
        }
        else {
            large->next = head;
            large = large->next;
            large->next = NULL;
            head = head->next;
        }
    }
    small->next = largehead->next;

    return smallhead->next;
}

ListNode结构体定义 #

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

输出差异的核心原因 #

两段代码的唯一区别在于处理当前节点时，head = head->next与small->next = NULL（或large->next = NULL）的执行顺序：

正确代码的逻辑 #

将当前节点挂到目标链表后，先把head指针移动到原链表的下一个节点，再切断当前节点与原链表的联系（置next为NULL）。这个顺序能保证后续遍历不会被打断——因为我们已经提前拿到了下一个要处理的节点地址，再切断当前节点的链接不会影响后续操作。

错误代码的逻辑 #

先切断当前节点与原链表的联系（置next为NULL），再移动head指针。此时head还指向当前节点，而当前节点的next已经被改成NULL，所以head = head->next会直接让head变为NULL，导致循环提前终止，原链表中剩下的节点完全没被处理。

举个实际例子：假设原链表是1->4->3->2->5->2，x=3。错误代码处理第一个节点1时，先把1->next设为NULL，再执行head = head->next，此时head直接变成NULL，循环结束。最终结果只会包含节点1，剩下的所有节点都未被处理，完全不符合分区要求。

内容的提问来源于stack exchange，提问作者Sajib Saha