LeetCode: Partition List

Simple Question with O(n) time.

1:  /*  
2:  ** This problem is solved by making 2 new heads,  
3:  ** one lead the nodes whose value are less than the target value;  
4:  ** one lead the others  
5:  ** After making two new lists, use 2 pointers to make a new lis.  
6:  ** Here we need to see that after finish these 2 lists, you  
7:  ** need to "NULL" these 2 lists at the end, or it will be TLE  
8:  */  
9:  public class Solution {  
10:    public ListNode partition(ListNode head, int x) {  
11:      if (head == null || head.next == null)   return head;  
12:      // Construct another 2 new List  
13:      ListNode newHead1 = new ListNode(0), newHead2 = new ListNode(0);  
14:      // 2 runners  
15:      ListNode p1 = newHead1, p2 = newHead2;  
16:      ListNode curr = head;  
17:      while (curr != null) {  
18:        if (curr.val < x) {  
19:          p1.next = curr;  
20:          p1 = p1.next;  
21:        }else {  
22:          p2.next = curr;  
23:          p2 = p2.next;  
24:        }  
25:        curr = curr.next;  
26:      }  
27:      p1.next = null;  
28:      p2.next = null;  
29:      p2 = newHead2.next;  
30:      while (true) {  
31:        if (p2 == null) {  
32:          p1.next = p2;  
33:          break;  
34:        }else {  
35:          p1.next = p2;  
36:          p1 = p1.next;  
37:          p2 = p2.next;  
38:        }  
39:      }  
40:      return newHead1.next;  
41:    }  
42:  }