92.reverse-linked-list-ii.md

92. Reverse Linked List II

Idea! We find the part to reverse and the before / after node of reverse list, reuse modified reverseLinkedList(node) with length to reverse, and relink the before / after node pointer to correct.

For example:

left = 2, right = 4
1 -> 2 -> 3 -> 4 -> 5
     L         R

// Traverse list to find the node of before left, after right and last node of reversed list
beforeLeft = 1
afterRight = 5
last = 2

// Reverse from left to right
reversedHead = reverseLinkedList(2 -> 3 -> 4), return 4

// Relink before and after pointer to reverse list
beforeLeft -> reversedHead -> ... -> last -> afterRight

fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
    if (head == null) return null

    // add sentinel
    val sentinel = ListNode(0)
    sentinel.next = head

    // iterate to locate the left, before left, right, after right node.
    var beforeLeft: ListNode? = null
    var afterRight: ListNode? = null
    // The last node after reversing
    var last: ListNode? = null
    var previous: ListNode? = sentinel
    var current: ListNode? = head
    var i = 1
    while (current != null) {
        if (i == left) {
            beforeLeft = previous         
            last = current       
        }
        if (i == right) {
            afterRight = current.next
            break
        }

        previous = current
        current = current.next
        i++
    }

    // reverse(left, right), return new head after reversed.
    val newHead = reverse(last, current)
    // val newHead = reverseLinkedList(start, right - left)
    // val newHead = reverse(leftNode, right - left + 1)

    // relink before left node to new head.
    beforeLeft?.next = newHead
    
    // relink the last node of revsered list to the node after right.
    last?.next = afterRight

    // return sentinel.next
    return sentinel.next
}

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

        previous = current
        current = next
    }
    return previous
}

// Alternative implementation of reverse by length
private fun reverse(node: ListNode?, length: Int): ListNode? {
    var i = 0
    var previous: ListNode? = null
    var current: ListNode? = node
    while (current != null && i <= length) {
        val next = current.next

        current.next = previous
        previous = current
        current = next
        i++
    }
    return previous
}

// Alternative implementation of reverse by counting
private fun reverse(start: ListNode?, count: Int): ListNode? {
    var previous: ListNode? = null
    var current: ListNode? = start
    var i = 0
    while (current != null && i < count) {
        val next = current?.next
        current?.next = previous
        previous = current
        current = next
        i++
    }
    return previous
}

One Pass

/**
     L              R
1 -> 2 -> 3 -> 4 -> 5 - 6
 */
class Solution {
    fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
        val sentinel = ListNode(-1)
        sentinel.next = head
        var previous: ListNode? = sentinel
        var current: ListNode? = head
        var i = 1
        while (i < left) {
            previous = current
            current = current?.next
            i++
        }

        // current is located at left
        val beforeLeft: ListNode? = previous
        val leftNode: ListNode? = current

        // beforeLeft = 1
        // leftNode = 2
        // i = 5
        // 1 -> 2 -> 3 -> 4 -> 5 -> 6
        //                p    c
        // 1 <- 2 <- 3 <- 4    5 -> 6
        while (i <= right) {
            val next = current?.next

            current?.next = previous
            previous = current
            current = next
            i++
        }

        // rightNode = 4
        // afterRight = 5
        val rightNode: ListNode? = previous
        var afterRight: ListNode? = current

        // 1 -> 4
        beforeLeft?.next = rightNode
        // 2 -> 5
        leftNode?.next = afterRight

        return sentinel.next
    }

    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
    }
}