Partition a singly linked list using Java 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 &amp;&amp; pRunner.next != null){
            if(pRunner.next.data &lt; 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;
        }
    }
}
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 &lt; 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.