148.sort-list.md

148. Sort List

Merge Sort

fun sortList(head: ListNode?): ListNode? {
    if (head == null || head?.next == null) return head
    val middle = findMiddle(head)
    val leftHead = sortList(head)
    val rightHead = sortList(middle)
    return merge(leftHead, rightHead)
}

private fun findMiddle(head: ListNode?): ListNode? {
    var fast: ListNode? = head
    var slow: ListNode? = head
    var previous: ListNode? = null
    while (fast?.next != null) {
        fast = fast?.next?.next
        previous = slow
        slow = slow?.next
    }
    // Disconnect the left part from the right part
    previous?.next = null
    return slow
}

private fun merge(leftHead: ListNode?, rightHead: ListNode?): ListNode? {
    val sentinel = ListNode(-1)
    var current: ListNode = sentinel
    var left: ListNode? = leftHead
        if (left.`val` <= right.`val`) {
            current.next = left
            left = left.next
        } else {
            current.next = right
            right = right.next
        }
        current = current.next
    }
    if (left != null) current.next = left
    if (right != null) current.next = right
    return sentinel.next
}

• Time Complexity: O(n lg n).
• Space Complexity: O(lg n) for recursive function calls.

Heap

private fun sortWithExtraSpace(head: ListNode?): ListNode? {
    val minHeap = PriorityQueue<ListNode>() { n1, n2 -> n1.`val` - n2.`val` }
    var node: ListNode? = head
    while (node != null) {
        val next = node.next
        node.next = null
        minHeap.add(node)
        node = next
    }
    
    val sentinel = ListNode(-1)
    node = sentinel
    while (minHeap.isNotEmpty()) {
        node?.next = minHeap.poll()
        node = node?.next
    }
    return sentinel.next
}

• Time Complexity: O(n lg n).
• Space Complexity: O(n).