LeetCode Solutions Blog

Reverse Nodes in k-Group

Number: 25

Difficulty: Hard

Paid? No

Problem Description

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list. k is a positive integer and is less than or equal to the length of the list. If the number of nodes is not a multiple of k then the remaining nodes at the end should remain as they are. The reversal must only change the links between nodes, not the values.

Key Insights

Use a dummy node to simplify edge cases.
Identify groups of k nodes using a helper function.
Reverse the nodes in each group using pointer manipulation.
If a remaining group has fewer than k nodes, leave it unchanged.
The reversal is done in-place with O(1) extra space.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes (each node is processed a constant number of times)
Space Complexity: O(1) (only constant extra space is used)

Solution

The solution involves iterating through the linked list by identifying groups of k consecutive nodes. For each group:

Find the kth node from the current starting point. If it does not exist, the remainder of the list is not reversed.
Reverse the nodes in the identified group in-place by adjusting the next pointers.
Reconnect the reversed group with the previous part of the list and update pointers to move to the next group. The approach leverages a dummy node for easier handling of head modifications and uses a helper function to fetch the kth node. The in-place reversal ensures that the extra memory usage is constant.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # Create a dummy node to simplify edge cases
        dummy = ListNode(0)
        dummy.next = head
        group_prev = dummy
        
        while True:
            # Find the kth node from group_prev
            kth = self.getKthNode(group_prev, k)
            if not kth:
                break
            group_next = kth.next
            
            # Reverse the group starting at group_prev.next up to kth
            prev = kth.next
            curr = group_prev.next
            while curr != group_next:
                temp = curr.next    # Store next node
                curr.next = prev    # Reverse pointer
                prev = curr         # Move prev forward
                curr = temp         # Move curr forward
            
            # Reconnect the reversed group with the previous part
            temp = group_prev.next   # temp is the start of the original group, becomes the new tail
            group_prev.next = kth    # Connect previous part to the kth node (new head of reversed group)
            group_prev = temp        # Move group_prev to the end of the reversed group
        
        return dummy.next
    
    # Helper function to get the kth node from the current node
    def getKthNode(self, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr