How does this linked list partitioning algorithm work?

Question

I'm reading right now the book Cracking the Coding Interview, which presents a linked list partition problem:

Given a linked list and a value x, partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

Assume that the linked list is not empty.

The solution is taken from the website GeeksForGeeks, and is identical to the second solution offered in the book CTCI:

// Function to make a new list  
// (using the existing nodes) and  
// return head of new list.  
static Node partition(Node head, int x)  
{  
    /* Let us initialize start and tail nodes of new list */
    Node tail = head;  
  
    // Now iterate original list and connect nodes  
    Node curr = head;  
    while (curr != null)  
    {  
        Node next = curr.next;  
        if (curr.data < x)  
        {  
            /* Insert node at head. */
            curr.next = head;  
            head = curr;  
        }  
  
        else // Append to the list of greater values  
        {  
            /* Insert node at tail. */
            tail.next = curr;  
            tail = curr;  
        }  
        curr = next;  
    }  
    tail.next = null;  
  
    // The head has changed, so we need  
    // to return it to the user.  
    return head;  
}

I don't understand this solution. How does this algorithm work? Why is it correct?

Answer 1

Try to think about like so:

Lets say this is our linked list (0) -> (1) -> (2) -> (-1) -> (1) -> (-5) (obviously linked lists don't look like this but for our example)

And x = 0

We do next = curr.next so that we don't "lose" the next node

\ I'm going to mark *head and ^tail

Now we look at (0) it doesn't matter if it's smaller than x (bcs its both head and tail) so its pointer is turned at itself

[*^(0)<  ] [  (1) -> (2) -> (-1) -> (1) -> (-5) ]

Now we look at (1) its not smaller than x either so (0) is pointed at it and it becomes ^tail

[ *(0) -> ^(1)< ] [ (2) -> (-1) -> (1) -> (-5) ] (the two lists are attached but lets imagine their not)

Same thing happens with (2) ^tail which is- (1) is pointed at it

[ *(0) -> (1) -> ^(2)<  ] [  (-1) -> (1) -> (-5) ]

Now we look at (-1) however this time it is smaller than x so its set to point at *head and then set to *head

[ *(-1) -> (0) -> (1) -> ^(2)<  ] [  (1) -> (-5) ]

And so on:

[ *(-1) -> (0) -> (1) -> (2) -> ^(1)<  ] [ (-5) ]

[ *(-5) -> (-1) -> (0) -> (1) -> (2) -> ^(1)<  ] [ ]