LinkedListProblem 25 of 36Important
Rotate a Doubly Linked list in group of Given Size [Very IMP]
Rotate a Doubly Linked List in Group of Given Size (Very Important)
Problem Statement
Given a doubly linked list containing n nodes, reverse the nodes in groups of k. If the number of nodes is not a multiple of k, the remaining nodes at the end should also be reversed.
Example
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8, k = 3
Output: 3 <-> 2 <-> 1 <-> 6 <-> 5 <-> 4 <-> 8 <-> 7
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5, k = 2
Output: 2 <-> 1 <-> 4 <-> 3 <-> 5
Brute Force Approach
Intuition
The brute force approach extracts values from each group of k nodes into an array, reverses the array, and puts the values back. This is simpler to implement but uses extra space.
Algorithm
- Traverse the list in groups of k
- For each group, extract values into an array
- Reverse the array
- Put values back into the nodes
- Move to the next group
Code
java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class ReverseInGroupsBrute {
public static Node reverseInGroupsBruteForce(Node head, int k) {
if (head == null || k <= 1) {
return head;
}
Node curr = head;
while (curr != null) {
List<Integer> values = new ArrayList<>();
Node groupStart = curr;
// Collect k values
for (int i = 0; i < k && curr != null; i++) {
values.add(curr.data);
curr = curr.next;
}
// Reverse the values
Collections.reverse(values);
// Put values back
Node temp = groupStart;
for (int val : values) {
temp.data = val;
temp = temp.next;
}
}
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" <-> ");
head = head.next;
}
System.out.println();
}
}Complexity Analysis
- Time Complexity: O(n) - We traverse each node once
- Space Complexity: O(k) - To store values of each group
Optimal Approach
Intuition
The optimal approach reverses the actual node connections within each group. We need to carefully manage the prev and next pointers for each node in the group and connect groups properly.
Algorithm
- For each group of k nodes:
- Reverse the pointers within the group
- Connect the reversed group to the previous group
- Track the new head of the entire list
- Handle the last group which may have fewer than k nodes
- Ensure all prev and next pointers are correctly set
Code
java
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class ReverseInGroupsOptimal {
public static Node reverseKNodes(Node head, int k) {
Node curr = head;
Node prev = null;
Node next = null;
int count = 0;
// Reverse k nodes
while (curr != null && count < k) {
next = curr.next;
curr.next = prev;
curr.prev = next;
prev = curr;
curr = next;
count++;
}
return prev; // New head of this reversed group
}
public static Node reverseInGroupsOptimal(Node head, int k) {
if (head == null || k <= 1) {
return head;
}
Node curr = head;
Node prevGroupTail = null;
Node newHead = null;
while (curr != null) {
// Count remaining nodes
int remaining = 0;
Node temp = curr;
while (temp != null && remaining < k) {
remaining++;
temp = temp.next;
}
// Save the start of this group (will be tail after reversal)
Node groupStart = curr;
// Move curr k nodes ahead
Node nextGroup = curr;
for (int i = 0; i < remaining; i++) {
nextGroup = nextGroup.next;
}
// Reverse this group
Node groupNewHead = reverseKNodes(curr, remaining);
// If this is the first group, set the new head
if (newHead == null) {
newHead = groupNewHead;
}
// Connect previous group to this group
if (prevGroupTail != null) {
prevGroupTail.next = groupNewHead;
groupNewHead.prev = prevGroupTail;
}
// Update prevGroupTail for next iteration
prevGroupTail = groupStart;
// Move to next group
curr = nextGroup;
}
// Fix the tail's next pointer
if (prevGroupTail != null) {
prevGroupTail.next = null;
}
return newHead;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data);
if (head.next != null) System.out.print(" <-> ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8
Node head = new Node(1);
Node curr = head;
for (int i = 2; i <= 8; i++) {
Node newNode = new Node(i);
curr.next = newNode;
newNode.prev = curr;
curr = newNode;
}
int k = 3;
System.out.print("Original list: ");
printList(head);
head = reverseInGroupsOptimal(head, k);
System.out.print("After reversing in groups of " + k + ": ");
printList(head);
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited once
- Space Complexity: O(1) - Only constant extra space used
Key Takeaways
- Group Management: Track the start and end of each group carefully
- Pointer Updates: In DLL, both prev and next need to be updated during reversal
- Connection Points: After reversing a group, the original head becomes tail and vice versa
- Inter-group Links: Connect groups by linking previous group's tail to current group's head
- Edge Cases: Handle groups smaller than k (typically the last group)
- Recursion vs Iteration: Iterative approach is preferred for O(1) space complexity
- Debugging Tip: Draw the pointers before and after each step to visualize changes