In this guide we will provide 25. Reverse Nodes in k-Group LeetCode Solution with best time and space complexity. The solution to Reverse Nodes in k-Group problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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 values in the list’s nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Constraints:
The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
25. Reverse Nodes in k-Group LeetCode Solution in C++
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr)
return nullptr;
ListNode* tail = head;
for (int i = 0; i < k; ++i) {
// There are less than k nodes in the list, do nothing.
if (tail == nullptr)
return head;
tail = tail->next;
}
ListNode* newHead = reverse(head, tail);
head->next = reverseKGroup(tail, k);
return newHead;
}
private:
// Reverses [head, tail).
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != tail) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
}; /* code provided by PROGIEZ */
25. Reverse Nodes in k-Group LeetCode Solution in Java
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode tail = head;
for (int i = 0; i < k; ++i) {
// There are less than k nodes in the list, do nothing.
if (tail == null)
return head;
tail = tail.next;
}
ListNode newHead = reverse(head, tail);
head.next = reverseKGroup(tail, k);
return newHead;
}
// Reverses [head, tail).
private ListNode reverse(ListNode head, ListNode tail) {
ListNode prev = null;
ListNode curr = head;
while (curr != tail) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
} // code provided by PROGIEZ
25. Reverse Nodes in k-Group LeetCode Solution in Python
class Solution:
def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
if not head:
return None
tail = head
for _ in range(k):
# There are less than k nodes in the list, do nothing.
if not tail:
return head
tail = tail.next
newHead = self._reverse(head, tail)
head.next = self.reverseKGroup(tail, k)
return newHead
def _reverse(
self,
head: ListNode | None,
tail: ListNode | None,
) -> ListNode | None:
"""Reverses [head, tail)."""
prev = None
curr = head
while curr != tail:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev #code by PROGIEZ
