0086. Partition List

https://leetcode.com/problems/partition-list

Description

Given the head of 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.

Example 1:

**Input:** head = [1,4,3,2,5,2], x = 3
**Output:** [1,2,2,4,3,5]

Example 2:

**Input:** head = [2,1], x = 2
**Output:** [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].

• -100 <= Node.val <= 100

• -200 <= x <= 200

ac1

modify in place

class Solution {
    public ListNode partition(ListNode head, int x) {
        // edge cases
        if (head == null || head.next == null) return head;

        //dummy, smallTail, prev, curr
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode smallTail = dummy, prev = dummy, curr = head;
        // walk
        while (curr != null) {
            if (curr.val < x && prev.val >= x) {
                // take out
                ListNode tmp = curr;
                prev.next = curr.next;
                curr = curr.next;
                // insert
                tmp.next = smallTail.next;
                smallTail.next = tmp;
                smallTail = smallTail.next;
            } else {
                prev = curr;
                curr = curr.next;
                if (smallTail.next.val < x) smallTail = smallTail.next;
            }
        }

        return dummy.next;
    }
}
// dummy, smallTail, prev, curr
// walk, when val < x, prev.next = curr.next, tmp = curr.
// insert tmp after smallTail

ac2

use two dummy node. this one is more concise and less error prone.

class Solution {
    public ListNode partition(ListNode head, int x) {
        // edge cases
        if (head == null || head.next == null) return head;

        //dummy, smallTail, prev, curr
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode curr1 = dummy1, curr2 = dummy2;
        // walk
        while (head != null) {
            if (head.val < x) {
                curr1.next = head;
                curr1 = curr1.next;
            } else {
                curr2.next = head;
                curr2 = curr2.next;
            }
            head = head.next;
        }

        curr2.next = null;
        curr1.next = dummy2.next;

        return dummy1.next;
    }
}