86. Partition List

Tags: ‘Linked List’, ‘Two Pointers’

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution

1. Use two extra list to store nodes
   • O(n) O(n) 7% 100%
   • 初次尝试debug了很久， 用curr循环时很容易出错（l1 为空或 l2 为空) ```java

public ListNode partition(ListNode head, int x) { if (head == null || head.next == null) return head; ListNode dummy = new ListNode(-1); dummy.next = head;

List<ListNode> l1 = new LinkedList<>();
List<ListNode> l2 = new LinkedList<>();

// populat l1 and l2
while (head != null) {
    if (head.val < x) {
        l1.add(head);
    } else {
        l2.add(head);
    }
    head = head.next;
}

ListNode curr = dummy;

// Point curr to the next node
if (!l1.isEmpty()) {
    curr.next = l1.get(0);
    // Loop through l1
    for (int i =0; i < l1.size() - 1; i++) {
        curr = l1.get(i);
        curr.next = l1.get(i + 1);
    }
    curr = l1.get(l1.size() - 1); // point curr to the end
} 

if (!l2.isEmpty()) {
    curr.next = l2.get(0);
    // loop through l2
    for (int i = 0; i < l2.size() - 1; i++) {
        curr = l2.get(i);
        curr.next = l2.get(i + 1);
    }
    curr = l2.get(l2.size() - 1); // point curr to the end
}

if (curr != null)curr.next = null;

return dummy.next; } ```

1. (BEST) Two Pointer, one pass using constant space

   public ListNode partition(ListNode head, int x) {
    ListNode before_dummy = new ListNode(-1);
    ListNode before = before_dummy;
    ListNode after_dummy = new ListNode(-1);
    ListNode after = after_dummy;
       
    while (head != null) {
        if (head.val < x) {
            before.next = head;
            before = before.next;
        } else {
            after.next = head;
            after = after.next;
        }
           
        head = head.next;
    }
    after.next = null;
    before.next = after_dummy.next; // connect two list;
       
    return before_dummy.next;
   }