Given the head of a singly linked list and an integer k
, reverse the nodes of the list k
at a time and return the new head of the reversed linked list. If the number of nodes in the linked list is not a multiple of k
, leave the remaining nodes as they are.
Table of Contents
Example:
Input:
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
k = 3
Output:
Reversed Linked List: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
Explanation: In the input, the linked list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
, and k = 3
. After reversing the nodes in groups of 3, the new linked list becomes 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
.
Solution in C++:
#include <iostream>
// Definition for singly-linked list
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Function to get the length of the linked list
int getLength(ListNode* head) {
int length = 0;
ListNode* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
// Function to reverse a linked list from position left to position right
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (head == nullptr || left == right) {
return head; // Nothing to reverse or invalid input
}
// Create a dummy node to handle the case where left = 1
ListNode* dummy = new ListNode(0);
dummy->next = head;
// Find the node at position (left - 1)
ListNode* prev = dummy;
for (int i = 1; i < left; ++i) {
prev = prev->next;
}
// Find the node at position right
ListNode* curr = prev->next;
ListNode* end = curr;
for (int i = left; i <= right; ++i) {
end = end->next;
}
// Reverse the sublist from position left to position right
while (curr != end) {
ListNode* nextNode = curr->next;
curr->next = end->next;
end->next = curr;
curr = nextNode;
}
// Connect the reversed sublist with the rest of the list
prev->next = end;
return dummy->next; // New head of the reversed sublist
}
// Function to reverse the linked list in k-groups
ListNode* reverseKGroup(ListNode* head, int k) {
int length = getLength(head);
int numGroups = length / k;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prevGroupEnd = dummy;
for (int i = 0; i < numGroups; ++i) {
int left = i * k + 1;
int right = left + k - 1;
head = reverseBetween(head, left, right);
prevGroupEnd->next = head;
for (int j = 0; j < k; ++j) {
prevGroupEnd = prevGroupEnd->next;
}
}
return dummy->next;
}
// Function to print the linked list
void printLinkedList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->val << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(6);
head->next->next->next->next->next->next = new ListNode(7);
head->next->next->next->next->next->next->next = new ListNode(8);
int k = 3;
std::cout << "Original Linked List: ";
printLinkedList(head);
ListNode* reversedHead = reverseKGroup(head, k);
std::cout << "Reversed Linked List: ";
printLinkedList(reversedHead);
return 0;
}
Explanation:
- The
reverseKGroup
function takes the head of the linked list and an integerk
as input and returns the new head of the reversed linked list ink
-groups. - We start by finding the total number of groups,
numGroups
, in the linked list based on the given value ofk
. - We use a dummy node,
dummy
, to handle the case wherek = 1
orhead
isnullptr
. - We use a
for
loop to reverse the linked list ink
-groups. For each group, we find theleft
andright
positions, and then reverse the sublist between these positions using thereverseBetween
function from the previous solution. - We update the previous group’s end node,
prevGroupEnd
, to point to the head of the newly reversed sublist. - We continue this process until all
numGroups
are reversed.
Time Complexity:
The time complexity of this solution is O(n), where n
is the number of nodes in the linked list. The reverseBetween
function is called for each group, and each group reversal takes linear time.
Space Complexity:
The space complexity of this solution is O(1) as we use a constant amount of additional space for variables. The reversal is done in-place without using any additional data structures.