25. Reverse Nodes in k-Group - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a linked list, 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 last remaining nodes should be left in their original order.
You may not alter the values in the nodes—only the nodes themselves may be changed.

Example 1:

Input: head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]
Explanation:
- The first group [1, 2] is reversed to [2, 1].
- The second group [3, 4] is reversed to [4, 3].
- The last node [5] remains as it is since the group size is less than 2.

Example 2:

Input: head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]
Explanation:
- The first group [1, 2, 3] is reversed to [3, 2, 1].
- The remaining group [4, 5] is left as is because its size is less than 3.

Constraints:

The number of nodes in the list is in the range [1, 5000].
1 ≤ k ≤ the length of the list.
The values of the nodes are not important for the reversal; only the nodes and their connections are changed.

Hints

Hint 1:
Think about how you would reverse a simple linked list. How can you adapt that to only reverse k nodes at a time?
Hint 2:
Use a dummy node to simplify edge cases (especially when the head of the list changes). You may need pointers to mark the beginning and end of the current k-group.
Hint 3:
Before reversing a group, ensure that there are at least k nodes remaining. If not, simply attach the remaining part without reversing.

Approach 1: Iterative Solution with Dummy Node

Idea

Count k Nodes:
For each group, first check whether there are k nodes available.
Reverse k Nodes:
Reverse the group of k nodes using the typical linked list reversal technique.
Link Groups:
After reversing, connect the reversed group to the previous part and set up for the next group.
Continue Until End:
Stop when there are fewer than k nodes left.

Detailed Steps

Setup a Dummy Node:
Create a dummy node that points to the head of the list. This simplifies handling edge cases where the head changes after reversal.
Initialize Pointers:
- prevGroupEnd initially points to the dummy node.
- groupStart points to the first node of the current group.
- Traverse to find groupEnd, which is the kth node of the current group.
Reverse the Group:
Reverse the nodes between groupStart and groupEnd.
Use three pointers (prev, curr, and next) to reverse the links.
Reconnect the List:
After reversing, connect the previous group’s end (prevGroupEnd) to the new start of the reversed group, and connect the old start (which becomes the end of the reversed group) to the next node after the group.
Move to Next Group:
Set prevGroupEnd to the end of the reversed group and repeat for the next group.

Visual Walkthrough

For the list: 1 → 2 → 3 → 4 → 5 and k = 2:

First Group:
- Group: 1 → 2
- Reverse to: 2 → 1
- Connect dummy → 2 → 1
Second Group:
- Next group: 3 → 4
- Reverse to: 4 → 3
- Connect 1 → 4 → 3
Remaining:
- Node 5 remains unchanged.
- Final list: dummy → 2 → 1 → 4 → 3 → 5

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- Every node is processed exactly once, and each group of k nodes is reversed in O(k) time.
- Overall time complexity: O(n), where n is the number of nodes in the list.
Space Complexity:
- The algorithm uses constant extra space aside from the recursion/iteration pointers.
- Overall space complexity: O(1).

Step-by-Step Walkthrough and Visual Example

Consider the list: 1 → 2 → 3 → 4 → 5 with k = 2.

Initial Setup:
- Dummy node points to 1.
- prevGroupEnd is the dummy node.
First Group (Nodes 1 and 2):
- Check that there are 2 nodes: nodes 1 and 2 exist.
- Reverse nodes 1 → 2 to get 2 → 1.
- Connect dummy → 2 → 1.
- Update prevGroupEnd to node 1 (the end of the reversed group).
Second Group (Nodes 3 and 4):
- Starting from node 3, confirm that 2 nodes are available.
- Reverse nodes 3 → 4 to get 4 → 3.
- Connect previous group's end (node 1) to node 4.
- Update prevGroupEnd to node 3.
Remaining Nodes:
- Only node 5 is left, which is less than k (2), so it remains as is.
- Final linked list: 2 → 1 → 4 → 3 → 5.

Common Mistakes and Edge Cases

Common Mistakes

Not Checking Group Length:
Failing to verify that a full group of k nodes exists before reversing can lead to an incorrect reversal of the last group.
Pointer Mismanagement:
Incorrectly updating the pointers during the reversal process may break the list connections.
Edge Case with k=1:
When k is 1, the list should remain unchanged. Ensure your solution handles this gracefully.

Edge Cases

k Equals 1:
The list remains unchanged.
k Equals the List Length:
The entire list is reversed.
Empty List:
Return null (or an empty list) when the input list is empty.

Variations

Reverse Linked List:
A simpler problem that involves reversing an entire linked list.
Reverse Nodes Between:
Reverse a part of the list between two given positions.

Merge Two Sorted Lists:
Practice handling linked list pointer manipulations.
Swap Nodes in Pairs:
A special case of k-group reversal with k = 2.