Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

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

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Note: the idea is to build two separate linked list, left and right. The left list stores the nodes which values are less than the given value, and the right list stores the nodes which values are greater than or equal to the given value. Insert the nodes to the corresponding lists one by one, then your program becomes easy to read!

01 public ListNode partition(ListNode head, int x) {
02     ListNode left=null;
03     ListNode leftEnd=null;
04     ListNode right=null;
05     ListNode rightEnd=null;
06     ListNode curr=head;
07     while(curr!=null)
08     {
09         ListNode next=curr.next;
10         curr.next=null;
11         if(curr.val<x)
12         {
13             if(left==null)
14             {
15                 left=curr;
16                 leftEnd=left;
17             }
18             else
19             {
20                 leftEnd.next=curr;
21                 leftEnd=leftEnd.next;
22             }
23         }
24         else
25         {
26             if(right==null)
27             {
28                 right=curr;
29                 rightEnd=right;
30             }
31             else
32             {
33                 rightEnd.next=curr;
34                 rightEnd=rightEnd.next;
35             }
36         }
37         curr=next;
38     }
39     if(left!=null)
40     {
41         leftEnd.next=right;
42         return left;
43     }
44     else
45     {
46         return right;
47     }
48 }