Skip to content

25.reverse-nodes-in-k-group.md

Latest commit

 

History

History
339 lines (285 loc) · 11.2 KB

25.reverse-nodes-in-k-group.md

File metadata and controls

339 lines (285 loc) · 11.2 KB

25. Reverse Nodes in k-Group

Hints

  • Can you reverse a sublist of length k in a linked list in-place?
  • What if the number of nodes left is less than k?
  • Think about how to connect the reversed group with the rest of the list.

Breakdowns

  1. How do you reverse a segment of a linked list?

Try to implement a helper function to reverse a segment [start, end].

  1. How do you process the list in groups of k?

Iterate through the list, each time checking if there are at least k nodes left. If so, reverse them; otherwise, leave the rest as is.

  1. How do you connect the reversed groups?

After reversing, make sure the previous group's tail points to the new head, and the new tail points to the next group.

Key Insights

  • This is a classic linked list reversal problem, but applied in fixed-size groups.
  • The sentinel node pattern is essential to handle head changes.
  • The in-place reversal of a sublist is a standard interview pattern.

Recursive

Recursively reverse the first k nodes, then call the function on the rest of the list. If there are fewer than k nodes left, leave them as is.

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null

    var size = 0
    var current = head
    while (current != null) {
        current = current.next
        size++
    }

    // Check if we have enough nodes to reverse
    if (size < k) return head

    // Start to reverse k nodes
    var previous: ListNode? = null
    current = head
    var i = 0
    while (current != null && i < k) {
        val next = current.next
        current.next = previous

        previous = current
        current = next
        i++
    }
    // previous: the last node of the current group, it will be the head of the reversed group
    val reversedHead = previous
    // current: the head of the next group after reversing the current group
    val reversedNext = reverseKGroup(current, k)
    head?.next = reversedNext

    return reversedHead
}

// Or equivalently
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null
    var i = 0
    var current: ListNode? = head
    while (current != null && i < k) {
        current = current.next
        i++
    }
    // Not enough k nodes to reverse
    if (i < k) return head

    // Start to reverse k nodes
    // First, recursively process the rest of the list
    var previous: ListNode? = reverseKGroup(current, k)
    
    // Now 'previous' holds the head of the reversed remaining part of the list
    // 'current' is reset to the head of the current k-group
    current = head
    i = 0
    while (current != null && i < k) {
        val next = current.next
        current.next = previous
        previous = current
        current = next
        i++
    }
    return previous
}
  • Time Complexity: O(N)
  • Space Complexity: O(N/k) for recursion stack (worst case O(N) if k=1).

In-place Iterative

We process the list one group of k nodes at a time, reverse each group in-place, and then reconnect it back into the list. There are several pointers to keep track of:

... -> groupPrev -> groupStart -> ... -> kthNode -> groupNext -> ...
       ^^^^^^^^)    (^^^^^^^^^^^^^^^^^^^^^^^^^^)    (^^^^^^^^
  previous group            current group           next group

We need 4 key pointers in each iteration:

Pointer Description
groupPrev Tail of the previous reversed group, it's used to stitch in the new head of current reversed group. Starts at sentinel node.
groupStart Head of the current group to reverse.
kthNode The k-th node in the current group (last node to reverse), it will become the new head after reversal.
groupNext Node after the current group (used to reconnect after reverse)

The final goals to reverse the current group:

  • groupPrev should link to kthNode.
  • groupStart should link to groupNext.
  • Each node in the current group should be reversed.
           |------------------------------|
           |                              v
... -> groupPrev  groupStart -> ... -> kthNode -> groupNext -> ...
                       |                              ^
                       |------------------------------|

// which is equivalent to
... -> groupPrev -> kthNode -> ... -> groupStart -> groupNext -> ...

The steps to reverse the current group:

  • Step 1.: Find the k-th node in the current group from groupPrev.
... -> groupPrev -> groupStart -> node2 -> ...  -> kthNode -> groupNext -> ...
                                                   ^^^^^^^
  • Step 2.: Reverse the current group: [groupStart, ... kth].
... -> groupPrev -> groupStart -> node2 -> ...  -> kthNode -> groupNext -> ...
                        |-----------------------------|
... -> groupPrev     kthNode -> ... -> node2 -> groupStart -> groupNext -> ...
  • Step 3.: Stitch in the new head of current reversed group. Now groupPrev.next is groupStart, we need to link it to kthNode. and move groupPrev to groupStart.
... -> groupPrev -> kthNode -> ... -> node2 -> groupStart -> groupNext -> ...
                                                   |   
                                              **groupPrev  
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null
    val sentinel = ListNode(-1)
    sentinel.next = head
    var groupPrev = sentinel
    while (true) {
        // Get the k-th node, if not enough nodes, break
        var kthNode = getKthNode(groupPrev, k) ?: break

        // Get the head of the current group
        val groupStart = groupPrev.next

        // Preserve the head of the next group
        val groupNext = kthNode?.next

        // Start to reverse the current group   
        var previous: ListNode? = groupNext
        var current: ListNode? = groupStart
        while (current != groupNext) {
            val next = current?.next
            current?.next = previous
            previous = current
            current = next
        }

        // Connect the previous group with the reversed current group
        groupPrev.next = kthNode
        // Update the previous group to the current group
        groupPrev = groupStart
    }
    return sentinel.next
}

// Move k times to get the k-th node
private fun getKthNode(head: ListNode?, k: Int): ListNode? {
    var current = head
    for (i in 0 until k) {
        current = current?.next ?: return null
    }
    return current
}

Example

// Original list
k = 3
s -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

// Locate the k-th node, and preserve the head of the next group
s -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
*              *    *
groupPrev      k    groupNext

// Start to reverse the current group
s -> 1 <- 2 <- 3    4 -> 5 -> 6 -> 7
     |              ^
     |--------------|

// Connect the previous group with the reversed current group
val next = groupPrev.next   // groupPrev = s, next = 1
groupPrev.next = kthNode    // s -> 3
groupPrev = next            // groupPrev = 1

// The result after the first iteration
s -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7

// ----------------
// Continue with the next group
s -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7
               *              *    *
               groupPrev      k    groupNext
  • Time Complexity: O(N), where N is the number of nodes (each node is visited and reversed once).
  • Space Complexity: O(1) (in-place, only a few pointers used).

Stack

The key ideas are the same as above, we just use a stack to reverse the nodes in each group. For each iteration, we push k nodes into the stack, and then pop them out to reverse the group. We keep track of two pointers:

  • current: The current node in the list. We move it k times to push it into the stack and check if there are enough k nodes left.
  • newCurrent: The last node to build the new list after reversing the current group.
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null
    val stack = Stack<ListNode>()
    val sentinel = ListNode(-1)
    sentinel.next = head
    var current = head
    var newCurrent = sentinel
    while (true) {
        var i = 0
        // Push `k` nodes into the stack
        while (i < k && current != null) {
            stack.push(current)
            current = current.next
            i++
        }
        // Not enough nodes to reverse
        if (i < k) {
            break
        }
        // Pop `k` nodes from the stack and build the new list
        while (stack.isNotEmpty()) {
            val node = stack.pop()
            newCurrent.next = node
            newCurrent = node
        }
        /**
         * Connect the new list with the next group
         * This is required otherwise the last node of the new list will point to
         * the last node of the current group, which will cause a cycle.
         * For example, list: 1 -> 2
         * stack = [1, 2]
         * newCurrent = 1 and break the loop, 1 still points to 2.
         */
        newCurrent.next = current
    }
    return sentinel.next
}
  • Time Complexity: O(N), where N is the number of nodes (each node is visited and reversed once).
  • Space Complexity: O(k) for the stack.

尾插法

TODO: The following solution is not correct.

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null
    val sentinel = ListNode(-1)
    sentinel.next = head

    var current = head
    var newCurrent = sentinel
    while (true) {
        var i = 0
        var start = current
        // Move to tail of current group
        while (i < k - 1 && current != null) {
            current = current.next
            i++
        }
        if (i < k - 1 || current == null) break

        val nextStart = current?.next

        // s -> 2 -> 1
        val tail = current!!
        newCurrent.next = tail
        newCurrent = tail

        // 1 -> 2
        // 2 -> 1
        while (start != tail) {
            newCurrent.next = start
            newCurrent = newCurrent.next!!
            start = start?.next
        }

        // Move to the head of next group
        newCurrent.next = nextStart
        current = nextStart
    }
    return sentinel.next
}

Edge Cases

  • List length < k:
    The last group should not be reversed.
    How to avoid? Always check if there are at least k nodes before reversing.
  • k = 1:
    The list should remain unchanged.
  • k = list length:
    The entire list is reversed once.
  • List with exactly k nodes:
    Should be reversed once.

Pitfalls

  • Off-by-one errors: When finding the k-th node, make sure to move k times from the current node, not k-1.
  • Losing references: Always keep track of the next group's head before reversing.
  • Not reconnecting the reversed group properly: After reversal, connect the previous group's tail to the new head, and the new tail to the next group.

Similar or Follow-up Problems