Reverse Nodes in k-Group

Hardlinked-listrecursion
Category: Linked List
Companies that ask this question:
AmazonFacebookGoogleMicrosoft
LeetCode →NeetCode →

Approach

Reverse Nodes in k-Group

Problem Statement

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 is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Approach: Iterative with Helper Function

The key is to reverse k nodes at a time while keeping track of connections.

Algorithm

  1. Count nodes: Check if we have k nodes remaining
  2. Reverse k nodes: Use standard linked list reversal
  3. Connect groups: Link the reversed group to previous and next groups
  4. Repeat: Continue until fewer than k nodes remain

Detailed Steps

For each group of k nodes:

  1. Find the kth node to check if we have enough nodes
  2. Reverse the k nodes in this group
  3. Connect:
    • Previous group's tail → current group's new head
    • Current group's tail → next group's head
  4. Move to the next group

Time Complexity

  • Time: O(n) where n is the number of nodes
    • We visit each node exactly once
  • Space: O(1) - only uses pointers

Visual Example

Input: 1→2→3→4→5, k=2

Group 1: Reverse [1,2]
  Before: 1→2→3→4→5
  After:  2→1→3→4→5

Group 2: Reverse [3,4]
  Before: 2→1→3→4→5
  After:  2→1→4→3→5

Group 3: [5] alone (< k nodes)
  Final:  2→1→4→3→5

Example with k=3

Input: 1→2→3→4→5, k=3

Group 1: Reverse [1,2,3]
  After: 3→2→1→4→5

Group 2: [4,5] alone (< k nodes)
  Final: 3→2→1→4→5

Key Insights

  1. Need helper function to reverse a portion of the list
  2. Must carefully track:
    • Previous group's tail
    • Current group's head and tail
    • Next group's head
  3. Edge cases:
    • List length < k: return as-is
    • k = 1: return as-is
    • Exact multiple of k: reverse all
  4. Only reverse nodes, don't modify values
  5. Leftover nodes (< k) remain unreversed

Alternative Approach: Recursive

Recursive solution is elegant but uses O(n/k) stack space.

Solution

java
1/**
2 * Reverse Nodes in k-Group
3 *
4 * Time Complexity: O(n)
5 * Space Complexity: O(1) for iterative
6 */
7
8class ListNode {
9    int val;
10    ListNode next;
11    ListNode() {}
12    ListNode(int val) { this.val = val; }
13    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
14}
15
16class Solution {
17    public ListNode reverseKGroup(ListNode head, int k) {
18        // Count total nodes
19        int count = 0;
20        ListNode curr = head;
21        while (curr != null) {
22            count++;
23            curr = curr.next;
24        }
25        
26        // Dummy node for easier head handling
27        ListNode dummy = new ListNode(0);
28        dummy.next = head;
29        ListNode prevGroupTail = dummy;
30        
31        while (count >= k) {
32            // Save the start of current group
33            ListNode groupStart = prevGroupTail.next;
34            
35            // Reverse k nodes
36            ListNode prev = null;
37            curr = groupStart;
38            for (int i = 0; i < k; i++) {
39                ListNode nextTemp = curr.next;
40                curr.next = prev;
41                prev = curr;
42                curr = nextTemp;
43            }
44            
45            // Connect with previous and next groups
46            prevGroupTail.next = prev;
47            groupStart.next = curr;
48            
49            // Move to next group
50            prevGroupTail = groupStart;
51            count -= k;
52        }
53        
54        return dummy.next;
55    }
56}
57
Loading visualizer...