cc150_2_4.java

/*
Created by bitcpf
*/


public class PartitionList {

	public static<Integer>  Node[] PartList(Node<Integer> head, int x){
		Node MidNode = head;
		Node next;
		Node LessHead = null;
		Node LargeHead = null;
		
		while(MidNode != null){
			next = MidNode.next;
			MidNode.next = null;
			if(MidNode.getval() < x){
				if(LessHead == null){
					LessHead = MidNode;
				}
				else{
					MidNode.next = LessHead;
					LessHead = MidNode;
				}
			}
			else{
				if(LargeHead == null){
					LargeHead = MidNode;
				}
				else{
					MidNode.next = LargeHead;
					LargeHead = MidNode;
				}
				
			}
		
			MidNode = next;
		}
		
		
		// Pack the two header in an array
		Node[] result = new Node[2];
		result[0] = LessHead;
		result[1] = LargeHead;
		return result;
	}
	
	public static void printlist(Node head){
		Node c_p = head;
		while(c_p.next != null){
			System.out.print(c_p.item + " ");
			c_p = c_p.next;
		}
		System.out.print(c_p.item);
	}
	
	public static void main(String[] args){
		// Initialize List
		int h = 4;
		Node head = new Node(h);
		Node current = head;
		for (int i = h + 1 ; i < 23; i++){
			current.next = new Node(i);
			current = current.next;
		}
		printlist(head);
		System.out.println("");
		Node[] test = PartList(head,10);
		printlist(test[0]);
		System.out.println("");
		printlist(test[1]);
	}
}

Node.java

public class Node<Item> {
	Item item = null;
	Node<Item> next = null;
	
	public Node (Item item){
		this.item = item;
		this.next = null;
	}
	
	public int getval(){
		return (Integer) this.item;
	}

}