这两个代码有什么区别，为什么它们给出不同的输出？

Question

问题陈述：给定链表的头和值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) {}
 * };

我只是想知道为什么这两个代码显示不同的输出。

Answer 1

之后

small->next = head;
small = small->next;

small

和

head

具有相同的值，因此

small->next = NULL;
head = head->next;

始终将

head

设置为

NULL

，因为第一行将

head->next

设置为

NULL

。

head = head->next;
small->next = NULL;

之所以有效，是因为它在将

head

设置为

next

之前将

next

移动到

NULL

。