Partition a singly linked list using Java

Question

This is my attempted solution to exercise 2.4 in Cracking the Coding Interview.

The problem statement is:

Write code to 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.

Example:

Input: \$ 3 \rightarrow 5 \rightarrow 8 \rightarrow 5 \rightarrow 10 \rightarrow 2 \rightarrow 1 \$

Output: \$ 3 \rightarrow 1 \rightarrow 2 \rightarrow 10 \rightarrow 5 \rightarrow 5 \rightarrow 8\$

I used the template code for a singly linked list from the book to write the Node class and I wrote the method partition and a JUnit test case for the method. I would appreciate any feedback on the algorithm for partition and the code overall.

Node.java

package practice_cracking_code_interview;

public class Node {
    Node next = null;
    int data;

    public Node(int d){
        data = d;
    }

    void appendToTail(int d){
        Node end = new Node(d);
        Node n = this;
        while(n.next != null ){
            n = n.next;
        }
        n.next = end;
    }

    Node partition(Node head, int x){
        Node pRunner = head;
        Node pHead = head;
        Node pTemp = null;

        while(pRunner != null && pRunner.next != null){
            if(pRunner.next.data < x){
                pTemp = pRunner.next.next;
                pRunner.next.next = pHead;
                pHead = pRunner.next;
                pRunner.next = pTemp;
            }
            else{
                pRunner = pRunner.next;
            }
        }
        return pHead;
    }
}

TestNode.java

package practice_cracking_code_interview;

import junit.framework.TestCase;

public class TestNode extends TestCase {

    public void testAppendToTail(){
        Node head = new Node(5);
        head.appendToTail(10);
        assertEquals(head.next.data, 10);
    }

    public void testPartitionOne(){
        Node head = new Node(3);
        head.appendToTail(5);
        head.appendToTail(8);
        head.appendToTail(5);
        head.appendToTail(10);
        head.appendToTail(2);
        head.appendToTail(1);
        Node n = head.partition(head, 5);

        int[] expected = new int[]{1, 2, 3, 5, 8, 5, 10};
        int i = 0;

        while(n != null){
            assertEquals(n.data, expected[i]);
            i++;
            n = n.next;
        }
    }

    public void testPartitionTwo(){
        Node head = new Node(3);
        head.appendToTail(5);
        head.appendToTail(8);
        head.appendToTail(5);
        head.appendToTail(10);
        head.appendToTail(2);
        head.appendToTail(1);
        Node n = head.partition(head, 11);

        int[] expected = new int[]{1, 2, 10, 5, 8, 5, 3};
        int i = 0;

        while(n != null){
            assertEquals(n.data, expected[i]);
            i++;
            n = n.next;
        }
    }
}

Answer 1

Not every variable is necessary

    Node partition(Node head, int x){
        Node pRunner = head;
        Node pHead = head;
        Node pTemp = null;

        while(pRunner != null && pRunner.next != null){

Since you only set pRunner to pRunner.next, it is enough to just check pRunner.next in the loop. We only need to check pRunner once.

    Node partition(Node head, int x) {
        if (head == null) {
            return null;
        }

        Node current = head;

        while (current.next != null) {

So check it once, prior to doing anything else. If null, we can go ahead and return immediately. An empty list is already partitioned.

We don't need separate head and pHead variables. You never use head after initializing other variables with it.

The pTemp variable isn't used outside the loop or across iterations, so it doesn't need to be declared outside the loop.

Using helper variables

            if(pRunner.next.data < x){
                pTemp = pRunner.next.next;
                pRunner.next.next = pHead;
                pHead = pRunner.next;
                pRunner.next = pTemp;
            }
            else{
                pRunner = pRunner.next;
            }

Consider

            Node next = current.next;
            if (next.data < x) {
                current.next = next.next;
                next.next = head;
                head = next;
            }
            else {
                current = next;
            }

The next variable simplifies constructs like current.next.data. But it also replaces the temp variable. Because next and current are separate, we can set current.next immediately rather than waiting until the end. And next will probably only exist as a register in the actual machine code. It's not alive long enough to need its own memory location.

I don't like that this reorders the list if called a second time. Obviously it has to reorder the list the first time, as that's what the operation does. But this will reorder the elements of an already partitioned list.

Avoid fragile tests

        int[] expected = new int[]{1, 2, 3, 5, 8, 5, 10};
        int i = 0;

        while(n != null){
            assertEquals(n.data, expected[i]);
            i++;
            n = n.next;
        }

This specifies a complete ordering of the data, but the problem doesn't. Yes, this is a correct ordering, but there are others. For example

3, 2, 1, 10, 8, 5, 5

Is an entirely valid ordering. But this test would fail it. Consider

        for (int i = 0; i < 3; i++) {
            assertNotNull(n);
            assertTrue(n.data < partitionValue);
            n = n.next;
        }

        for (int i = 3; i < 7; i++) {
            assertNotNull(n);
            assertFalse(n.data < partitionValue);
            n = n.next;
        }

This tests the actual assertion, that the list would be partitioned such that the first three elements were less than the partitionValue and the next four were not. So if you changed the function to preserve the original ordering within each partition, this would pass. The current test would fail.

1, 2, 3, 10, 5, 8, 5

does not match int[] expected = new int[]{1, 2, 3, 5, 8, 5, 10};.

Or note that the example output in the question would not match the test although it is a valid ordering of the input.

One advantage of the current version is that it tells you what element it finds that it should not have found there. But you can restore that behavior if you want. Consider

            String message = "Found " + n.data + " at " + i + " which is less than " + partitionValue;
            assertFalse(message, n.data < partitionValue);

You can control what message is shown if you want. So use that to make the message informative if you need that.

Answer 2

The only suggestions I have are:

• make the implementation look as "obvious,"
• guarantee stability: the elements belonging in one of the sublists will preserve their relative order.

And this is what I had in mind:

public class MyList {

    private static final class MyListNode {
        int value;
        MyListNode next;

        MyListNode(int value) {
            this.value = value;
        }
    }

    private MyListNode head;
    private MyListNode tail;

    public void add(int value) {
        MyListNode newnode = new MyListNode(value);

        if (tail == null) {
            head = newnode;
        } else {
            tail.next = newnode;
        }

        tail = newnode;
    }

    public void partition(int pivot) {
        MyListNode smallListHead = null;
        MyListNode smallListTail = null;
        MyListNode largeListHead = null;
        MyListNode largeListTail = null;

        while (head != null) {
            // Remove the head node H:
            MyListNode currentNode = head;
            head = head.next;

            // Decide to which of the two lists to append the node H:
            if (currentNode.value < pivot) {
                if (smallListTail == null) {
                    smallListHead = currentNode;
                } else {
                    smallListTail.next = currentNode;
                }

                smallListTail = currentNode;
            } else {
                if (largeListTail == null) {
                    largeListHead = currentNode;
                } else {
                    largeListTail.next = currentNode;
                }

                largeListTail = currentNode;
            }
        }

        if (smallListHead == null) {
            head = largeListHead;
        } else if (largeListHead == null) {
            head = smallListHead;
        } else {
            head = smallListHead;
            smallListTail.next = largeListHead;
            tail = largeListTail;
            // Marks the end of the list, otherwise might be a cycle:
            largeListTail.next = null; 
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder().append('[');
        String separator = "";

        for (MyListNode node = head; node != null; node = node.next) {
            sb.append(separator).append(node.value);
            separator = ", ";
        }

        return sb.append(']').toString();
    }

    public static void main(final String... args) {
        MyList list = new MyList();

        list.add(3);
        list.add(5);
        list.add(8);
        list.add(5);
        list.add(10);
        list.add(2);
        list.add(1);

        System.out.println(list);
        list.partition(5);
        System.out.println(list);
        list.partition(0);
        System.out.println(list);
        list.partition(100);
        System.out.println(list);

        list = new MyList();
        list.partition(1);
        System.out.println(list);
    }
}

What comes to the complexity of my alternative, it is, at least, not worse than yours. As an additional fun, you could consider implementing quicksort for linked lists using the partition procedure you have.

Hope that helps.