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?