143.reorder-list.md

143. Reorder List

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

// size is even
1 -> 2 -> 3 -> 4
// break into two lists, and reverse the second list
1 -> 2
4 -> 3

// side is odd
1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> null
5 -> 4 -> 3

Edge / Corner Cases

• Size 1 might cause circular list.

Input: [1]
Output: [1]

Implementation

fun reorderList(head: ListNode?): Unit {
    // size = 1 should not run the following code which leads to circular list.
    if (head == null || head?.next == null) return
    val middle = findMiddle(head)
    val newHead = reverse(middle)

    var first: ListNode? = head
    var second: ListNode? = newHead
    while (first != null && second != null) {

        val firstNext = first?.next
        first?.next = second
        first = firstNext

        // For size is odd, in case the second node is pointed to the first node which is null.
        // 1  2  null
        // | /| /
        // 5  4   3

        // We should keep as the following:
        // 1  2  null
        // | /| 
        // 5  4 -> 3
        
        // Or we can break the while loop when first is null.
        // if (first == null) break
        
        if (first != null) {
            val secondNext = second?.next
            second?.next = first
            second = secondNext
        }
    }
}

private fun findMiddle(head: ListNode): ListNode {
    var fast: ListNode? = head
    var slow: ListNode = head
    var beforeMiddle: ListNode? = null
    while (fast != null && fast.next != null) {
        beforeMiddle = slow
        fast = fast?.next?.next
        slow = slow.next
    }
    // Disconnect the list into two parts.
    beforeMiddle?.next = null
    return slow
}

private fun reverse(head: ListNode?): ListNode? {
    var previous: ListNode? = null
    var current: ListNode? = head
    while (current != null) {
        val next = current.next
        current.next = previous
        previous = current
        current = next
    }
    return previous
}