Partition List

Problem : Given a linked list and a value X. Partition it so that all the nodes with values smaller than X comes before the nodes with value greater than or equal to X.

You should preserve the original relative order of nodes in each of two partitions.

For ex: 

Given 1 -> 4 -> 3 -> 2-> 5-> 2 and X = 3.

Return 1 -> 2 -> 2 -> 4 -> 3 -> 5.

Basic idea is to create a temp list and iterate through the original list with a pre and curr pointer. While iterating if a node with value greater or equal than X is found, disconnect this node from the original list and add it to temp list. in the end connect the temp list with the end of original list. This will preserve the relative order also.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public class Solution { public ListNode partition(ListNode head, int x) { if(head == null || head.next == null){ return head; } ListNode curr = head; ListNode fakePre = new ListNode(0); fakePre.next = head; ListNode pre = fakePre; ListNode fakeHead = new ListNode(0); ListNode temp2 = fakeHead; while(curr!=null){ if (curr!=null && curr.val < x){ pre = pre.next; curr = curr.next; }else{ //found a node with value greater than or //equal to x, so add it to temp2 list and move temp2 by one temp2.next = curr; temp2 = temp2.next; // delete this node from the current list. So, point the pre's->next to pre->next->next // and curr will become the next node. (pre's->next->next now is pre's->next) pre.next = pre.next.next; curr = pre.next; } } temp2.next = null; pre.next = fakeHead.next; return fakePre.next; } }