Skip to content

25. Reverse Nodes in k-GroupΒΆ

Problem Link

This problem requires reversing nodes of a linked list in groups of size \(k\), while leaving any remaining nodes (fewer than k) unchanged. Since the list must be modified in-place, we need careful pointer manipulation. The key idea is to process the list one group at a time:

  • Check whether a full group of \(k\) nodes exists.
  • Reverse exactly those \(k\) nodes.
  • Reconnect the reversed group back to the rest of the list.
  • Move on to the next group.

reverse_nodes_in_k_group.png We start by creating a dummy node that points to the head of the list. This simplifies edge cases, especially when the first group is reversed. A pointer group_prev is used to track the node just before the current group.

Finding the k-th Node: Before reversing a group, we must ensure that there are at least k nodes available. The helper function _getNode(curr, k) moves k steps forward from group_prev to find the k-th node of the group.

  • If the \(k^{th}\) node does not exist, we stop processing and return the list as-is.
  • Otherwise, we record group_next, which points to the node immediately after the current group.

Reversing the Group: To reverse the current group, we use the standard in-place reversal technique used previously. Setting prev to group_next ensures that, after reversal, the last node of the group correctly points to the next group.

Reconnecting the Group: After reversing, kth_node becomes the new head of the reversed group and the original head of the group becomes the tail. So we can update group_prev.next to point to kth_node and move group_prev to the tail of the reversed group to prepare for the next iteration

This process repeats until fewer than k nodes remain. The final list is returned starting from dummy.next.

Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the list

Space: \(O(1)\)

class Solution:
    def _getNode(self, curr, n):
        while curr and n > 0:
            curr = curr.next
            n-=1
        return curr

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth_node = self._getNode(group_prev, k)
            if not kth_node:
                break
            group_next = kth_node.next

            prev, curr = group_next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            tmp = group_prev.next
            group_prev.next = kth_node
            group_prev = tmp
        return dummy.next

func getKthNode(node *ListNode, k int) *ListNode {
    for node != nil && k > 0 {
        node = node.Next
        k--
    }
    return node
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Val: -1, Next: head}
    group_prev := dummy
    var kthNode, group_next, prev, curr, temp *ListNode
    for true {
        kthNode = getKthNode(group_prev, k)
        if kthNode == nil {
            break
        }

        group_next = kthNode.Next
        prev, curr = group_next, group_prev.Next
        for curr != group_next {
            temp = curr.Next
            curr.Next = prev
            prev = curr
            curr = temp
        }

        temp = group_prev.Next
        group_prev.Next = kthNode
        group_prev = temp
    }
    return dummy.Next
}