- we need to reverse the nodes of the list k at a time
- if there are fewer than k nodes left, they should remain in place
- the solution will most likely involve a two pass approach:
1. count the total number of nodes in the list
2. reverse in groups of k, while trakcing previous and next pointer
🤔What Did I Struggle With?
categorization of the problem as a hard is due to the complexity involved in the swapping logic and pointer manipulation of the linked list
💡 Explanation of Solution
1. create a dummy node pointing to the head of the list to simplify edge cases
2. count the number of nodes in the linked list
3. use three pointers (prev, curr, next) to help with reversing
4. for every k group
- move next to track the next node to be reversed
- reverse the k nodes by iterating k-1 times
- update prev to be the lat node of the versed group
5. repeat until there are fewer than k nodes left
6. return the modified list
⌛ Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
💻 Implementation of Solution
class Solution {public: ListNode* reverseKGroup(ListNode* head, int k) { if (!head || k == 1) return head; ListNode* dummy = new ListNode(0); dummy->next = head; ListNode *curr = dummy, *prev = dummy, *next = dummy; int count = 0; // Count the number of nodes in the list while (curr->next) { curr = curr->next; count++; } // Reverse every k nodes while (count >= k) { curr = prev->next; next = curr->next; // Reverse k nodes for (int i = 1; i < k; i++) { curr->next = next->next; next->next = prev->next; prev->next = next; next = curr->next; } prev = curr; count -= k; } return dummy->next; }};