LinkedListProblem 2 of 36
Reverse a Linked List in group of Given Size [Very Imp]
Reverse a Linked List in Groups of Given Size
Problem Statement
Given a linked list, reverse the nodes of the linked 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, the remaining nodes at the end should remain as they are.
Example
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]
Input: head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]
Input: head = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [3, 2, 1, 6, 5, 4, 7, 8]
Brute Force Approach (Recursive)
Intuition
We can solve this recursively by reversing the first k nodes, then recursively processing the rest of the list. The recursive call handles the remaining groups automatically.
Algorithm
- Check if there are at least k nodes remaining
- If yes, reverse the first k nodes
- Recursively call the function for the remaining list
- Connect the reversed group to the result of recursive call
- Return the new head
Implementation
Complexity Analysis
- Time Complexity: O(n) - Each node is visited at most twice
- Space Complexity: O(n/k) - Recursive call stack depth
Optimal Approach (Iterative)
Intuition
We can solve this iteratively using a dummy node and carefully managing pointers. For each group of k nodes, we reverse them in place and connect the groups properly.
Algorithm
- Create a dummy node pointing to head
- Use pointers to track: groupPrev (node before current group), groupEnd (last node of current group)
- For each group:
- Find the kth node (groupEnd)
- If less than k nodes remain, break
- Save the node after the group
- Reverse the current group
- Connect previous group to new head
- Connect tail to next group
- Return dummy.next
Visualization
Initial: dummy -> 1 -> 2 -> 3 -> 4 -> 5, k = 2
↑
groupPrev
After reversing first group:
dummy -> 2 -> 1 -> 3 -> 4 -> 5
↑
groupPrev
After reversing second group:
dummy -> 2 -> 1 -> 4 -> 3 -> 5
↑
groupPrev
Implementation
Complexity Analysis
- Time Complexity: O(n) - Each node is visited at most twice
- Space Complexity: O(1) - Only using constant extra space
Key Takeaways
- Dummy node technique simplifies edge case handling when the head might change
- Breaking the problem into smaller steps: find kth node → reverse group → connect groups
- The iterative solution is preferred for O(1) space complexity
- Keep track of the node before each group to properly connect reversed groups
- This is a very important interview problem that tests pointer manipulation skills
- Variant: If remaining nodes should also be reversed, simply remove the length check