Problem Statement in English

You’re given the head of a linked list and an integer k. You need to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, then the remaining nodes should remain as they are.

Approach

We can split this into 2 smaller subproblems:

  1. Reversing a linked list: We can reverse a linked list using an iterative approach. We maintain three pointers: prev, curr, and next. We iterate through the list, reversing the next pointer of each node to point to the previous node. You can check out the Reverse Linked List problem for more details on this.

  2. Reversing nodes in groups of k: We can iterate through the linked list and reverse every group of k nodes. We need to keep track of the previous group’s tail and the next group’s head to reconnect the reversed groups properly.

And we’re done!

Solution in Python


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse(start_node):
            prev = None
            curr = start_node
            while curr:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            return prev

        # Dummy node to handle head updates cleanly
        dummy = ListNode(0)
        dummy.next = head
        group_prev = dummy

        while True:
            # 1. Find the k-th node from group_prev
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next  # Fewer than k nodes left

            # 2. Save pointers to next group & start of current group
            group_next = kth.next
            group_start = group_prev.next

            # 3. Disconnect group and reverse it
            kth.next = None
            reverse(group_start)

            # 4. Reconnect reversed group with previous and next parts
            group_prev.next = kth          # kth is now the head of reversed sublist
            group_start.next = group_next  # group_start is now the tail

            # 5. Move group_prev pointer forward for the next iteration
            group_prev = group_start

Complexity

  • Time: $O(n)$
    Since we are traversing the linked list once to reverse the nodes in groups of k, the time complexity is linear with respect to the number of nodes in the list.

  • Space: $O(k)$
    Since we are using a recursive function to reverse the nodes, the space complexity is proportional to the size of the group being reversed, which is k. However, if we implement the reversal iteratively, we can achieve $O(1)$ space complexity.

Mistakes I Made

I messed up the pointer manipulation.

And we are done.