// D. Scott
// CCI - Problem 2.4
// Partition a singly linked list around a particular value 
// (here partition = 8)

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


public static void main (String[] args)
{
    // generate list
    Node list = new Node(19);
    Node head = list;
    list.appendToTail(5);
    list.appendToTail(2);
    list.appendToTail(19);
    list.appendToTail(1);
    list.appendToTail(6);
    list.appendToTail(8);
    list.appendToTail(33);
    list.appendToTail(14);
    list.appendToTail(9);
    
    // print original list:
    System.out.println("Original list:")
    count = 0;
    while (list != null) {
        count++;
        System.out.println(count + ". " + list.data);
        list = list.next;
    }
    list = head;

    // selection partition value
    int partition = 8;
    Node list2 = new Node(0);
    
    // pass 1: store values less than partition
    int added = 0;
    while (list != null) {
        if (list.data < partition) {
            // for first node only: edit, don't append
            if (added == 0) {
                list2.data = list.data;
                added++;
            } else {
            // subsequent nodes: append
            list2.appendToTail(list.data);
            }
        }
        list = list.next;
    } 
    
    // pass 2: store values >= partition:
    list = head;
    while (list != null) {
        if (list.data >= partition)
            list2.appendToTail(list.data);
        list = list.next;
    }
    
    // print partitioned list:
    System.out.println("\nPartitioned list:")
    count = 0;
    boolean partition_found = false;
    while (list2 != null) {
        count++;
        if (partition_found == false && list2.data >= partition) {
            System.out.println("----------");
            partition_found = true;
        }
            System.out.println(count + ". " + list2.data);
            list2 = list2.next;
    }
        
}