86.partition-list.md

86. Partition List

We just iterate through the list and add the nodes to the small or large list, then we join the two lists together.

fun partition(head: ListNode?, x: Int): ListNode? {
    if (head == null) return null
    val smallSentinel = ListNode(-1)
    var small: ListNode? = smallSentinel
    val largeSentinel = ListNode(-1)
    var large: ListNode = largeSentinel

    var current: ListNode? = head
    while (current != null) {
        val next = current.next
        // We need to break the link between current and next
        // 1 -> 7 -> 2

        // small: 1 -> 2
        // larget: 7 -> 2 (if we don't break the link)

        current.next = null
        if (current.`val` < x) {
            small?.next = current
            small = small?.next
        } else {
            large?.next = current
            large = large?.next
        }
        current = next
    }
    small?.next = largeSentinel.next
    return smallSentinel.next
}

• Time Complexity: O(n)
• Space Complexity: O(1)