How to Solve Reverse Nodes in k-Group
Reverse Nodes in k-Group Introduction
Reverse Nodes in k-Group Introduction
The Reverse Nodes in k-Group problem asks us to reverse the nodes of the given linked list k at a time and return the modified list. This problem can be solved using a recursive approach.
Reverse Nodes in k-Group Problem
Reverse Nodes in k-Group Problem
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 Inputs and Outputs
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]
Reverse Nodes in k-Group Solutions
Reverse Nodes in k-Group Solutions
To solve this problem, we use a recursive approach. We go through the linked list, considering k nodes at a time. If there are fewer than k nodes remaining, we leave them as they are without reversing. However, when we have k nodes, we reverse them by changing their next pointers. This reversal process involves carefully keeping track of the previous and next pointers.
Once we reverse the k nodes, the head of the reversed portion becomes the last node of the original k nodes, and we update its next pointer to point to the result of reversing the remaining list. We repeat this process until we reach the end of the linked list. By doing this, we gradually reverse the linked list in groups of k nodes.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
if not head or not head.next:
return head
count = 0
curr = head
# Check if the number of nodes is a multiple of k
while curr and count < k:
curr = curr.next
count += 1
if count < k: # Number of nodes is less than k
return head
# Reverse the first k nodes
curr = head
prev = None
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Recursively reverse the remaining list
head.next = reverseKGroup(curr, k)
return prev
# Driver code and test cases
# Test Case 1: Reverse groups of 2 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 2 -> 1 -> 4 -> 3 -> 5 -> None
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
k1 = 2
reversed_list1 = reverseKGroup(head1, k1)
while reversed_list1:
print(reversed_list1.val, end=" -> ")
reversed_list1 = reversed_list1.next
print("None")
# Test Case 2: Reverse groups of 3 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 3 -> 2 -> 1 -> 4 -> 5 -> None
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)
head2.next.next.next.next = ListNode(5)
k2 = 3
reversed_list2 = reverseKGroup(head2, k2)
while reversed_list2:
print(reversed_list2.val, end=" -> ")
reversed_list2 = reversed_list2.next
print("None")1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def reverseKGroup(head, k):
7 if not head or not head.next:
8 return head
9
10 count = 0
11 curr = head
12
13 # Check if the number of nodes is a multiple of k
14 while curr and count < k:
15 curr = curr.next
16 count += 1
17
18 if count < k: # Number of nodes is less than k
19 return head
20
21 # Reverse the first k nodes
22 curr = head
23 prev = None
24 for _ in range(k):
25 nxt = curr.next
26 curr.next = prev
27 prev = curr
28 curr = nxt
29
30 # Recursively reverse the remaining list
31 head.next = reverseKGroup(curr, k)
32
33 return prev
34
35
36# Driver code and test cases
37# Test Case 1: Reverse groups of 2 nodes
38# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
39# Output: 2 -> 1 -> 4 -> 3 -> 5 -> None
40head1 = ListNode(1)
41head1.next = ListNode(2)
42head1.next.next = ListNode(3)
43head1.next.next.next = ListNode(4)
44head1.next.next.next.next = ListNode(5)
45k1 = 2
46reversed_list1 = reverseKGroup(head1, k1)
47while reversed_list1:
48 print(reversed_list1.val, end=" -> ")
49 reversed_list1 = reversed_list1.next
50print("None")
51
52# Test Case 2: Reverse groups of 3 nodes
53# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
54# Output: 3 -> 2 -> 1 -> 4 -> 5 -> None
55head2 = ListNode(1)
56head2.next = ListNode(2)
57head2.next.next = ListNode(3)
58head2.next.next.next = ListNode(4)
59head2.next.next.next.next = ListNode(5)
60k2 = 3
61reversed_list2 = reverseKGroup(head2, k2)
62while reversed_list2:
63 print(reversed_list2.val, end=" -> ")
64 reversed_list2 = reversed_list2.next
65print("None")Time/Space Complexity Analysis
- Time Complexity: O(N), where n is the number of nodes in the linked list. In the worst case, we need to reverse all the nodes in the linked list. It's important to note that the algorithm performs a constant amount of work per node, and the number of nodes processed remains the same regardless of the group size k. So, the time complexity does not depend on the value of k.
- Space Complexity: O(1), because regardless of the size of the linked list or the group size, the amount of addition space remains used constant.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
