086. Partition List

Posted on | In

Solution 1: accepted 1ms

Keep a tail pointer when we need the end node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode partition(ListNode head, int x) {
    ListNode leftHead = new ListNode(0);        
    ListNode left = leftHead;        
    ListNode rightHead = new ListNode(0);
    ListNode right = rightHead;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = null;
        if (head.val < x) {
            left.next = head;
            left = head;
        } else {
            right.next = head;
            right = head;
        }
        head = next;
    }
    left.next = rightHead.next; // left = leftHead if no elements were sorted to left
    return leftHead.next;
}