Given the head a linked list, the task is to reverse every k node in the linked list. If the number of nodes is not a multiple of k then the left-out nodes in the end, should be considered as a group and must be reversed.
Examples:
Input: head = 1 -> 2 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8, k = 4 Output: 4 -> 2 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5
Explanation: The first 4 elements 1, 2, 2, 4 are reversed first and then the next 4 elements 5, 6, 7, 8. Hence, the resultant linked list is 4 -> 2 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5.
Input: head = 1 -> 2 -> 3 -> 4 -> 5, k = 3 Output: 3 -> 2 -> 1 -> 5 -> 4
Explanation: The first 3 elements 1, 2, 3 are reversed first and then left out elements 4, 5 are reversed. Hence, the resultant linked list is 3 -> 2 -> 1 -> 5 -> 4.
1 <= k <= size of linked list
Approach 01:
-
C++
-
Python
class Solution {
public:
static Node* reverseKGroup(Node* head, int k) {
if (k == 1) return head; // No reversal needed if k is 1
return reverseHelper(head, head, k);
}
private:
// Helper function to manage reversal of groups
static Node* reverseHelper(Node* groupHead, Node* groupEnd, int groupSize) {
if (groupEnd == nullptr) {
return nullptr; // End of the list
}
Node* tail = groupHead; // Tail of the current group
groupEnd = findGroupEnd(groupEnd, groupSize); // Move to the end of the current group
Node* nextGroup = reverseHelper(groupEnd, groupEnd, groupSize); // Recursively reverse remaining groups
Node* reversedGroup = reverseList(groupHead); // Reverse the current group
tail->next = nextGroup; // Connect the reversed group with the next group
return reversedGroup;
}
// Function to reverse a linked list
static Node* reverseList(Node* head) {
Node* current = head;
Node* previous = nullptr;
Node* nextNode = nullptr;
while (current != nullptr) {
nextNode = current->next;
current->next = previous;
previous = current;
current = nextNode;
}
return previous; // New head of the reversed list
}
// Function to move to the end of a group of size `groupSize`
static Node* findGroupEnd(Node* current, int groupSize) {
int count = 0;
while (current != nullptr && count < groupSize) {
current = current->next;
++count;
// Break the link at the end of the group
if (count == groupSize - 1 && current != nullptr && current->next != nullptr) {
Node* temp = current;
current = current->next;
temp->next = nullptr;
++count;
}
}
return current;
}
};
class Solution:
@staticmethod
def reverseKGroup(head, k):
if k == 1: # No reversal needed if k is 1
return head
return Solution.reverseHelper(head, head, k)
@staticmethod
def reverseHelper(groupHead, groupEnd, groupSize):
if groupEnd is None:
return None # End of the list
tail = groupHead # Tail of the current group
groupEnd = Solution.findGroupEnd(groupEnd, groupSize) # Move to the end of the current group
nextGroup = Solution.reverseHelper(groupEnd, groupEnd, groupSize) # Recursively reverse remaining groups
reversedGroup = Solution.reverseList(groupHead) # Reverse the current group
tail.next = nextGroup # Connect the reversed group with the next group
return reversedGroup
@staticmethod
def reverseList(head):
current = head
previous = None
while current:
nextNode = current.next
current.next = previous
previous = current
current = nextNode
return previous # New head of the reversed list
@staticmethod
def findGroupEnd(current, groupSize):
count = 0
while current and count < groupSize:
current = current.next
count += 1
# Break the link at the end of the group
if count == groupSize - 1 and current and current.next:
temp = current
current = current.next
temp.next = None
count += 1
return current
Time Complexity:
- Reversal of Groups:
Each group of size \( k \) is reversed in \( O(k) \). If there are \( n \) nodes in the list, the total number of groups is approximately \( n/k \). Hence, the total time complexity for reversing all groups is \( O(n) \).
- Finding Group End:
The
findGroupEndfunction traverses \( k \) nodes for each group, contributing \( O(n) \) in total for all groups. - Overall Time Complexity:
The combined time complexity is \( O(n) \), as all operations are linear with respect to the number of nodes.
Space Complexity:
- Recursive Calls:
Each recursive call to
reverseHelperprocesses one group. In the worst case, there are \( n/k \) recursive calls, leading to a maximum recursion stack depth of \( O(n/k) \). - Auxiliary Space:
The reversal process and group traversal do not use extra space beyond the recursion stack, keeping additional space usage at \( O(1) \).
- Overall Space Complexity:
The total space complexity is \( O(n/k) \) due to the recursion stack.