CareerCup_2.4 - ListPartition

ListPartition.java

package Chapter2;

public class ListPartition {

    public static void partition(MyLinkedList<Integer> list, int x) {
	if (list == null || list.head == null)
	    return;
	Node<Integer> cur = list.head;
	Node<Integer> leftHead = null, leftTail = null;
	Node<Integer> rightHead = null;

	// partition list into two lists
	while (cur != null) {
	    Node<Integer> next = cur.next;
	    if (cur.data < x) {
		if (leftHead == null) {
		    leftTail = cur;
		}
		cur.next = leftHead;
		leftHead = cur;
	    } else {
		cur.next = rightHead;
		rightHead = cur;
	    }
	    cur = next;
	}

	// connect two partitioned list
	if (leftTail != null) {
	    leftTail.next = rightHead;
	    list.head = leftHead;
	} else {
	    list.head = rightHead;
	}
    }

    public static void main(String[] args) {
	MyLinkedList<Integer> list = new MyLinkedList<>(new Integer[] { 1, 2,
		11, 7, 5, 77, 3, 22, 5, 16 });
	list.print();
	partition(list, 10);
	list.print();
    }
}

MyLinkedList.java

package Chapter2;

//Singly Linked List
public class MyLinkedList<T> {
    public Node<T> head;

    public MyLinkedList(Node<T> h) {
	head = h;
    }
    
    public MyLinkedList() {
	head = null;
    }

    public MyLinkedList(T[] dataArray) {
	if (dataArray == null || dataArray.length <= 0)
	    return;
	head = new Node<>(dataArray[0], null);
	Node<T> node = head;
	for (int i = 1; i < dataArray.length; i++) {
	    node.next = new Node<T>(dataArray[i], null);
	    node = node.next;
	}
    }

    public void print() {
	Node<T> cur = head;
	while (cur != null) {
	    System.out.print(cur.data);
	    if (cur.next != null) {
		System.out.print(" -> ");
	    }
	    cur = cur.next;
	}
	System.out.println();
    }

    public void prepend(T data) {
	Node<T> next = head != null ?  head.next : null;
	head = new Node<T>(data, next);
    }

    public MyLinkedList<T> reverse() {
	if(head == null) return null;
	Node<T> newHead = head;
	Node<T> cur = head.next;
	head.next = null;
	while(cur != null) {
	    Node<T> next = cur.next;
	    cur.next = newHead;
	    newHead = cur;
	    cur = next;
	}
	head = newHead;
	return this;
    }
}

Node.java

package Chapter2;

public class Node<T> {
    public T data;
    public Node<T> next;
    
    public Node(T d, Node<T> n){
	data = d;
	next = n;
    }
}