Partition List

1. Problem Description

Given the head head of a linked list and a value x, partition the list so that all nodes with values less than x come before nodes with values greater than or equal to x.

Preserve the original relative order of the nodes in each partition.

2. Approach

Similar to the partition step in quicksort.

3. Implementation

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    leftDummyHead := &ListNode{}
    rightDummyHead := &ListNode{}
    l := leftDummyHead
    r := rightDummyHead

    current := head
    for current != nil {
        next := current.Next
        current.Next = nil
        if current.Val < x {
            l.Next = current
            l = l.Next
        } else {
            r.Next = current
            r = r.Next
        }
        current = next
    }

    l.Next = rightDummyHead.Next
    return leftDummyHead.Next
}

4. References

• 86. Partition List - LeetCode