Partition List

 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  */ 
12 public class Solution {
13     /**
14      * @param head: The first node of linked list.
15      * @param x: an integer
16      * @return: a ListNode 
17      */
18     public ListNode partition(ListNode head, int x) {
19         ListNode left = new ListNode(0);
20         ListNode right = new ListNode(0);
21         
22         ListNode leftHead = left;
23         ListNode rightHead = right;
24         
25         while (head != null) {
26             if (head.val < x) {
27                 left.next = head;
28                 left = head;
29             } else {
30                 right.next = head;
31                 right = head;
32             }
33             head = head.next;
34         }
35         left.next = rightHead.next;
36         right.next = null;
37         return leftHead.next;
38     }
39 }