25. Reverse Nodes in k-Group
Problem Description
In this problem, we are given the head of a linked list and an integer k. The task is to reverse every consecutive k nodes in the linked list. If the number of nodes is not a multiple of k, then the remaining nodes at the end of the list should stay in the same order. It is important to note that we can only change the links between nodes, not the node values themselves. This process is similar to reversing the entire linked list, but it's done in chunks of k elements at a time.
Intuition
The key to solving this problem lies in breaking it down into smaller, more manageable tasks. Here's how we can think about it:
-
Divide the list into segments: We treat the list as a sequence of segments each with
knodes, except possibly the last segment which may have less thanknodes if the list's length is not a multiple ofk. -
Reverse individual segments: We reverse each segment of
knodes while ensuring to maintain the connection with the rest of the list. This means detaching the segment, reversing it, and then reconnecting it with the main list. -
Re-connect segments: Once a segment is reversed, it is necessary to attach the tail of the segment (which was originally the head) to the next part of the list which may be the head of the next segment to be reversed or the remaining part of the list.
-
Handle the end case: When we reach the end of the list and there are fewer than
knodes left, we simply retain their order and attach that segment as it is to the previously processed part of the list.
The intuition behind the solution approach comes from recognizing that this problem is a modification of a standard linked list reversal algorithm. In a typical linked list reversal, we reverse the links between nodes until we reach the end of the list. In this case, we apply the same principle but in a more controlled manner where the reversal stops after k nodes and we take extra care to attach the reversed segment back to the main list.
Learn more about Recursion and Linked List patterns.
How does quick sort divide the problem into subproblems?
Solution Approach
The solution approach can be broken down into the following steps:
-
Set up a dummy node: We start by creating a dummy node, which serves as a preceding node to the head of the linked list. This allows us to easily manipulate the head of the list (which may change several times as we reverse segments) without worrying about losing the reference to the start of the list.
-
Initialize pointers: We set up two pointers,
preandcur, that initially point to the dummy node. Theprepointer will be used to keep track of the node at the beginning of the segment we’re about to reverse, andcurwill be used to traverseknodes ahead to find the end of the segment. -
Find segments to reverse: We move the
curpointerknodes ahead to confirm that we have a full segment to reverse. If we reach the end of the list before movingksteps, we know that we're on the last segment, and thus we simply return the list without modifying this last part. -
Reverse the segment: Once a full segment of
knodes has been confirmed by thecurpointer, we temporarily detach this segment from the rest of the list. We call thereverseListhelper function, which reverses the segment using the classic three-pointer approach for reversing a linked list (pre,p,q). -
Reconnect segments: After reversing the segment, we need to reconnect it with the main list. This involves setting the
nextpointer of the last node of the reversed segment (previously the first) to point tot, which is the node following thecurnode (the end of the segment being reversed). Thenextpointer ofpre(which was the tail of the previous segment) is then updated to point to thepre.next = reverseList(start)which returns the new head of the reversed segment. -
Preparation for next iteration: Finally,
preis moved to the end of the reversed segment (which was its starting node), andcuris reset topre. This ensures that we are ready to process the next segment.
The pattern used in this solution could be described as a modified two-pointer technique where one pointer (cur) is used to identify the segment to be reversed, and another pointer (pre) is used to manage connections between reversed segments. The algorithm efficiently manipulates references within the list, never requiring more than a constant amount of additional space, which leads to its space complexity of O(1).
The reversal of each segment is a classic linked list reversal process that is applied repeatedly to each segment determined by our two-pointer setup. The time complexity of the overall algorithm is O(n) because each node is looked at a constant number of times (once when identifying the segment and once when actually reversing it).
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Example Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have a linked list and k = 2:
1Original List: 1 -> 2 -> 3 -> 4 -> 5 2 3We are expected to reverse every two nodes: 4Desired Outcome: 2 -> 1 -> 4 -> 3 -> 5
-
Set up a dummy node:
- We initiate the dummy node and link it to the head of the list:
dummy -> 1 -> 2 -> 3 -> 4 -> 5.
- We initiate the dummy node and link it to the head of the list:
-
Initialize pointers:
prepoints todummy, andcuralso points todummy.
-
Find segments to reverse:
- We move
curtwo steps, after whichcurpoints to the node2. - We verify that there is a full segment of
knodes (1and2) to reverse.
- We move
-
Reverse the segment:
- We detach the segment
1 -> 2, and we reverse it, such that it becomes2 -> 1. - The rest of the list is temporarily disconnected, so we have
dummy -> 2 -> 1and then3 -> 4 -> 5.
- We detach the segment
-
Reconnect segments:
- We connect the node
1(which is the tail of the reversed segment) to node3(which is the next node on the list). - Now the list is
dummy -> 2 -> 1 -> 3 -> 4 -> 5.
- We connect the node
-
Preparation for the next iteration:
- We move the
prepointer to the end of the reversed segment (node1), and resetcurtopre. - The list remains as
dummy -> 2 -> 1 -> 3 -> 4 -> 5.
- We move the
We then repeat steps 3 to 6 for the next segment:
- By moving
curpointer two steps, we havecurat node4, confirming a full segment (3and4). - We then reverse the
3 -> 4segment to get4 -> 3. - The list is reconnected to become
dummy -> 2 -> 1 -> 4 -> 3 -> 5. - Once we prepare for the next iteration, there is only one node left (node
5), which doesn't form a full segment ofk=2, so it remains as it is.
- Final Reconnecting:
- The list is now fully processed and connected:
dummy -> 2 -> 1 -> 4 -> 3 -> 5.
- The list is now fully processed and connected:
Since the dummy node was used solely for pointer manipulation, the final list's head is the node following the dummy, which is 2. Therefore, the final output of the list after the algorithm is applied is 2 -> 1 -> 4 -> 3 -> 5, which matches our desired outcome.
Solution Implementation
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
8 # Helper function to reverse a linked list
9 def reverse_list(node):
10 prev, current = None, node
11 while current:
12 next_temp = current.next
13 current.next = prev
14 prev = current
15 current = next_temp
16 return prev
17
18 # The dummy node is used to handle edge cases smoothly
19 dummy = ListNode()
20 dummy.next = head
21 prev_group = dummy
22
23 while head:
24 # Check if there is a full group to reverse
25 count = 0
26 current = head
27 while count < k and current:
28 current = current.next
29 count += 1
30
31 # If we have k nodes, proceed to reverse
32 if count == k:
33 # Detach the k group and reverse it
34 k_group_end = head
35 for _ in range(k - 1): # Move to the end of the k group
36 k_group_end = k_group_end.next
37 next_group = k_group_end.next
38 k_group_end.next = None
39 new_group_head = reverse_list(head)
40
41 # Connect the reversed group back to the list
42 prev_group.next = new_group_head
43 head.next = next_group
44
45 # Move prev_group and head for the next round of reversal
46 prev_group = head
47 head = next_group
48 else:
49 # Not enough nodes to fill a k group, so we are done
50 break
51
52 # Return the new head of the modified list
53 return dummy.next
541class Solution {
2 public ListNode reverseKGroup(ListNode head, int k) {
3 // A dummy node with 0 as value and pointing to the head of the list
4 ListNode dummyNode = new ListNode(0, head);
5 ListNode predecessor = dummyNode, current = dummyNode;
6
7 // Iterate through the list
8 while (current.next != null) {
9 // Check if there are k nodes to reverse
10 for (int i = 0; i < k && current != null; i++) {
11 current = current.next;
12 }
13 // If less than k nodes remain, no more reversing is needed
14 if (current == null) {
15 return dummyNode.next;
16 }
17
18 // Temporarily store the next segment to be addressed after reversal
19 ListNode temp = current.next;
20 // Detach the k nodes from the rest of the list
21 current.next = null;
22 // 'start' will be the new tail after the reversal
23 ListNode start = predecessor.next;
24 // Reverse the k nodes
25 predecessor.next = reverseList(start);
26 // Connect the new tail to the temp segment stored before
27 start.next = temp;
28 // Move the predecessor and current pointers k nodes ahead
29 predecessor = start;
30 current = predecessor;
31 }
32 return dummyNode.next;
33 }
34
35 /**
36 * Helper method to reverse the linked list.
37 *
38 * @param head The head of the list to be reversed.
39 * @return The new head of the reversed list.
40 */
41 private ListNode reverseList(ListNode head) {
42 ListNode previous = null, currentNode = head;
43
44 // Traverse the list and reverse the links
45 while (currentNode != null) {
46 ListNode nextNode = currentNode.next;
47 currentNode.next = previous;
48 previous = currentNode;
49 currentNode = nextNode;
50 }
51 // Return the new head of the reversed list
52 return previous;
53 }
54}
551// Definition for singly-linked list node
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode(int x) : val(x), next(nullptr) {}
6};
7
8/**
9 * Reverses a portion of a linked list from a start node to an end node, both inclusive.
10 * @param start - The first node in the sequence to be reversed.
11 * @param end - The last node in the sequence to be reversed.
12 * @returns A pair where the first element is the new head and the second is the new tail.
13 */
14std::pair<ListNode*, ListNode*> reverse(ListNode* start, ListNode* end) {
15 ListNode* current = start;
16 ListNode* prev = end->next;
17 // Iteratively reverse nodes until the end is reached
18 while (prev != end) {
19 ListNode* temp = current->next;
20 current->next = prev;
21 prev = current;
22 current = temp;
23 }
24 return {end, start}; // The start becomes the new end, and the end becomes the new start
25}
26
27/**
28 * Reverses nodes in k-group.
29 * @param head - The head of the linked list.
30 * @param k - The size of the group to reverse nodes within.
31 * @returns The head of the modified linked list after k-group reversals.
32 */
33ListNode* reverseKGroup(ListNode* head, int k) {
34 ListNode dummyNode(0); // Dummy node to simplify edge cases
35 dummyNode.next = head;
36 ListNode* predecessor = &dummyNode;
37
38 while (head != nullptr) {
39 ListNode* tail = predecessor;
40
41 // Find the k-th node from the head or end if there are less than k nodes left
42 for (int i = 0; i < k; ++i) {
43 tail = tail->next;
44 if (tail == nullptr) {
45 return dummyNode.next; // Less than k nodes, return the list as is
46 }
47 }
48
49 ListNode* nextGroupHead = tail->next;
50 // Reverse the current group of k nodes
51 auto reversed = reverse(head, tail);
52
53 // Connect the reversed group with the rest of the list
54 predecessor->next = reversed.first;
55 reversed.second->next = nextGroupHead;
56
57 // Move the pointers to the next group of nodes
58 predecessor = reversed.second;
59 head = nextGroupHead;
60 }
61
62 return dummyNode.next; // Return the new head of the list
63}
641// Definition for singly-linked list node
2interface ListNode {
3 val: number;
4 next: ListNode | null;
5}
6
7/**
8 * Reverses a portion of a linked list from a start node to an end node, both inclusive.
9 * @param start - The first node in the sequence to be reversed.
10 * @param end - The last node in the sequence to be reversed.
11 * @returns A tuple where the first element is the new head and the second is the new tail.
12 */
13function reverse(start: ListNode, end: ListNode): [ListNode, ListNode] {
14 let current = start;
15 let prev = end.next;
16 // Iteratively reverse nodes until the end is reached
17 while (prev !== end) {
18 let temp = current.next;
19 current.next = prev;
20 prev = current;
21 current = temp;
22 }
23 return [end, start];
24}
25
26/**
27 * Reverses nodes in k-group.
28 * @param head - The head of the linked list.
29 * @param k - The size of the group to reverse nodes within.
30 * @returns The head of the modified linked list after k-group reversals.
31 */
32function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
33 let dummyNode = { val: 0, next: head }; // Dummy node to simplify edge cases
34 let predecessor = dummyNode;
35
36 while (head !== null) {
37 let tail = predecessor;
38
39 // Find the k-th node from the head or end if there are less than k nodes left
40 for (let i = 0; i < k; ++i) {
41 tail = tail.next!;
42 if (tail == null) {
43 return dummyNode.next;
44 }
45 }
46
47 let nextGroupHead = tail.next;
48 // Reverse the current group of k nodes
49 [head, tail] = reverse(head, tail);
50
51 // Connect the reversed group with the rest of the list
52 predecessor.next = head;
53 tail.next = nextGroupHead;
54
55 // Move the pointers to the next group of nodes
56 predecessor = tail;
57 head = nextGroupHead;
58 }
59
60 return dummyNode.next; // Return the new head of the list
61}
62How many ways can you arrange the three letters A, B and C?
Time and Space Complexity
The time complexity of the given code can be understood by analyzing the two main operations it performs: traversal of the linked list and reversal of each k-sized group.
-
Traversal Time Complexity:
To ascertain whether a k-group can be reversed, the list is traversed in segments up to
knodes. This check is carried outn/ktimes wherenis the total number of nodes in the list. If a full group ofknodes is found, a reversal is performed; if not, the remaining nodes are left as is. -
Reversal Time Complexity:
For each k-group identified, a reversal is performed. The reversal operation within a group of size
kis O(k). Since there aren/ksuch groups in the list, the total time taken for all reversals amounts tok * (n/k) = n.
Therefore, the combined time complexity for traversing and reversing the linked list in k-groups is O(n), where n is the total number of nodes in the linked list.
Space Complexity:
The space usage of the algorithm comes from the variables that hold pointers and the recursive call stack when reversing the linked list. Since the reversal is done iteratively here, there is no additional space complexity due to recursion.
The iterative approach only uses a fixed number of pointers (pre, p, q, cur, start, t, and dummy), so the space complexity is O(1), which is constant and does not depend on the number of nodes in the linked list or the group size k.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.