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 k nodes, except possibly the last segment which may have less than k nodes if the list's length is not a multiple of k.
Reverse individual segments: We reverse each segment of k nodes 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 k nodes 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.

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, pre and cur, that initially point to the dummy node. The pre pointer will be used to keep track of the node at the beginning of the segment we’re about to reverse, and cur will be used to traverse k nodes ahead to find the end of the segment.
Find segments to reverse: We move the cur pointer k nodes ahead to confirm that we have a full segment to reverse. If we reach the end of the list before moving k steps, 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 k nodes has been confirmed by the cur pointer, we temporarily detach this segment from the rest of the list. We call the reverseList helper 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 next pointer of the last node of the reversed segment (previously the first) to point to t, which is the node following the cur node (the end of the segment being reversed). The next pointer of pre (which was the tail of the previous segment) is then updated to point to the pre.next = reverseList(start) which returns the new head of the reversed segment.
Preparation for next iteration: Finally, pre is moved to the end of the reversed segment (which was its starting node), and cur is reset to pre. 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).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have a linked list and k = 2:

Original List: 1 -> 2 -> 3 -> 4 -> 5

We are expected to reverse every two nodes:
Desired 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.
Initialize pointers:
- pre points to dummy, and cur also points to dummy.
Find segments to reverse:
- We move cur two steps, after which cur points to the node 2.
- We verify that there is a full segment of k nodes (1 and 2) to reverse.
Reverse the segment:
- We detach the segment 1 -> 2, and we reverse it, such that it becomes 2 -> 1.
- The rest of the list is temporarily disconnected, so we have dummy -> 2 -> 1 and then 3 -> 4 -> 5.
Reconnect segments:
- We connect the node 1 (which is the tail of the reversed segment) to node 3 (which is the next node on the list).
- Now the list is dummy -> 2 -> 1 -> 3 -> 4 -> 5.
Preparation for the next iteration:
- We move the pre pointer to the end of the reversed segment (node 1), and reset cur to pre.
- The list remains as dummy -> 2 -> 1 -> 3 -> 4 -> 5.

We then repeat steps 3 to 6 for the next segment:

By moving cur pointer two steps, we have cur at node 4, confirming a full segment (3 and 4).
We then reverse the 3 -> 4 segment to get 4 -> 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 of k=2, so it remains as it is.

Final Reconnecting:
- The list is now fully processed and connected: dummy -> 2 -> 1 -> 4 -> 3 -> 5.

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
54

1class 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}
55

1// 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}
64

1// 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}
62

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 k nodes. This check is carried out n/k times where n is the total number of nodes in the list. If a full group of k nodes 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 k is O(k). Since there are n/k such groups in the list, the total time taken for all reversals amounts to k * (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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know