Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its 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 it is. You may not alter the nodes, only pointers can be changed.
Constraints:
- 1 <= k <= length of the linked list
- 0 <= length of the linked list <= 5000
- -5000 <= Node.val <= 5000
Examples:
Input: [1,2,3,4,5] and k = 2
Output: [2,1,4,3,5]
Explanation: The first two nodes are reversed, then the next two nodes are reversed, and the last node remains the same.
Input: [1,2,3,4,5] and k = 3
Output: [3,2,1,4,5]
Explanation: The first three nodes are reversed, and the last two nodes remain the same.
Solutions
Iterative Approach
The solution uses an iterative approach to reverse the nodes in k-group. It uses a dummy node to simplify the code and a pre pointer to keep track of the previous node. It counts the number of nodes in the current group and if it is equal to k, it reverses the nodes in the group.
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
while (pre) {
int count = 0;
ListNode* temp = pre;
while (temp->next && count < k) {
temp = temp->next;
count++;
}
if (count == k) {
ListNode* curr = pre->next;
ListNode* next = nullptr;
for (int i = 0;
i < k;
i++) {
next = curr->next;
curr->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = curr;
}
else {
break;
}
}
return dummy->next;
}Follow-up:
Reverse Nodes in k-Group II
