Partition List

Problem Summary

Given the head of a linked list and a value x, partition it so that all nodes with values less than x come before all nodes with values greater than or equal to x, while preserving the original relative order within each partition.

Constraints:

The list has between 0 and 200 nodes.
Node values are integers in the range [-100, 100], and x is in the range [-200, 200].

Techniques

Linked List
Two Pointers

Solution

import { ListNode } from "../list-node"

function partition(head: ListNode | null, x: number): ListNode | null {
    let minor = new ListNode(-1, undefined)
    let major = new ListNode(-1, undefined)
    let currentMinor = minor
    let currentMajor = major
    let current = head

    while(current) {
        if (current.val < x) {
            currentMinor.next = current
            currentMinor = currentMinor.next
        } else {
            currentMajor.next = current
            currentMajor = currentMajor.next
        }

        current = current.next
    }

    head = minor.next ? minor.next : head
    currentMinor.next = major.next
    currentMajor.next = null

    return head
};