-4

Problem Statement: Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

First Code that provides correct output

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;
    }

Second Code that provides wrong output

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;
    }

And this is the defination of ListNode Structure

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) {}
 * };

I just want to know why these two codes show different output.

Sajib Saha
  • 1
  • In the `if` block, the `small` pointer becomes the same as the `head` pointer (the statement `small = small->next;` really is doing `small = head`). In the wrong version of the code, you first set its `next` field to `nullptr`, and then move `head` to it, making it `nullptr`. That's not what you want to happen. You want `head` to move to the next node **before** you break that link. – trincot Aug 15 '23 at 07:21
  • 4
    But honestly, this becomes trivial when you use a debugger and step through the code. – trincot Aug 15 '23 at 07:24
  • Draw boxes and arrows with pen(cil) and paper and trace through the code. – molbdnilo Aug 15 '23 at 07:26
  • You should read [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – Jesper Juhl Aug 15 '23 at 08:36

1 Answers1

3

After

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

small and head have the same value therefore

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

will always set head to NULL as the first line sets head->next to NULL.

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

Works because it moves head to next before setting next to NULL.

Alan Birtles
  • 32,622
  • 4
  • 31
  • 60