Reverse Nodes in k-Group

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 linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Examples

Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or k == 1:
        return head
    
    # Count nodes in the list
    count = 0
    curr = head
    while curr:
        count += 1
        curr = curr.next
    
    # Create dummy node
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    # Process k nodes at a time
    while count >= k:
        curr = prev.next
        next_node = curr.next
        
        # Reverse k nodes
        for i in range(k - 1):
            curr.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node
            next_node = curr.next
        
        prev = curr
        count -= k
    
    return dummy.next

Java Solution


// Java solution would go here.

C++ Solution


//C++ Solution would go here.

JavaScript Solution


//Javascript solution would go here.

C# Solution


//C# solution would go here.

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the linked list
Space Complexity: O(1) as we only use a constant amount of extra space

Solution Explanation

This solution reverses the linked list k nodes at a time. Here's how it works:

First, count total nodes to know how many complete groups of k exist
For each group of k nodes:
- Reverse the k nodes using iterative reversal
- Connect the reversed group with the rest of the list
- Move to the next group
Leave any remaining nodes (less than k) unchanged

Key points:

Use a dummy node to handle the case of reversing the head
Carefully manage pointers during reversal
Only reverse complete groups of k nodes
Handle edge cases (empty list, k=1) properly