Q2_4.java

public class Q2_4 {
	public static void main(String args[]) {
		Node test = arrayToLinkedList(new int[] { 5, 2, 3, 4, 1, 2 });
		Node output = sortLList(test, 3);
		System.out.println(compareLinkedList(output, arrayToLinkedList(new int[] { 2,1,2,5,3,4 })));
	}

	public static Node sortLList(Node root, int val) {
		Node head = root, cursor = root;
		while (cursor.value < val && cursor.next != null) {
			cursor = cursor.next;
		}		
		while (cursor.next != null) {			
			if (cursor.next.value < val) {
				Node newHead = new Node(cursor.next.value);
				newHead.next = head;
				head = newHead;
				cursor.next = cursor.next.next;
			} else
				cursor = cursor.next;
		}
		return head;
	}

	private static Node arrayToLinkedList(int[] array) {
		Node head = new Node(array[0]);
		Node current = head;
		for (int i = 1; i < array.length; i++) {
			current.next = new Node(array[i]);
			current = current.next;
		}
		return head;
	}

	private static boolean compareLinkedList(Node root1, Node root2) {
		do {
			if (root1 == null && root2 == null)
				return true;
			if (root1 == null || root2 == null)
				return false;
			if (root1.value != root2.value)
				return false;
			root1 = root1.next;
			root2 = root2.next;
		} while (true);
	}
}