25. Reverse Nodes in k-Group

Reverse Nodes in k-Group

Problem Description

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  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?

To give an example, given a LinkedList with values of [1, 2, 3, 4, 5, 6] , we previously reversed all pairs to get [2, 1, 4, 3, 6, 5] . Now, however, we might be passed reverse-group-size value (k) of 3, which would cause the LinkedList to become [3, 2, 1, 6, 5, 4] , or 4, which would create [4, 3, 2, 1, 5, 6] (because there aren’t enough nodes to reverse the 2nd set of 4 nodes).

To help understand the below solutions, we will split this problem into two parts.

The first part is to identify blocks of ListNodes that need reversing. If we have 5 nodes in our LinkedList and have been given a k value of 2, then we know we can reverse the nodes [1, 2] (to get [2, 1]), and [3, 4] (to get [4, 3]), but 5 will be left as is, giving us a final output of [2, 1, 4, 3, 5]. Likewise, if we’re given a k of 4, then we must reverse [1, 2, 3, 4] (to get [4, 3, 2, 1]) but do not have enough nodes for the second batch of reversal, so we’re left with [4, 3, 2, 1, 5].

The second part is the actual reversal. In order to reverse a LinkedList, we’ll need to point each ListNode to its predecessor, and then point the final node to the node that follows. Back To Back, SWE did a great video on this that I’d recommend watching, as it's a difficult concept to explain here.

Approach) Recursive

we reverse the first k elements of the passed in LinkedList and call the function again on the rest of the LinkedList. If the rest of the LinkedList is k or more elements long, another reversal is carried out on that segment, and the process continues. 
If not, the last part of the LinkedList is returned in its original order, and the overall LinkedList is then returned.

Code:

var reverseKGroup = function (head, k) {
    // Create a pointer which will traverse the head
    let curr = head;

    // Create a counter to determine how many nodes we have traversed
    let count = 0;

    // Loop until we find either the end of the LinkedList, or the k + 1 node
    while (curr != null && count != k) {
        curr = curr.next;
        count++;
    }

    // If we have found the k + 1 node
    if (count == k) {
        // Attempt to reverse the next k nodes (will return the value of curr if not enough nodes)
        curr = reverseKGroup(curr, k); // reverse list with k+1 node as head

        // Loop through the number of nodes in this group
        while (count-- > 0) {
            // Flip the nodes to point in the opposite direction (reverse them)
            let tmp = head.next;
            head.next = curr;
            curr = head;
            head = tmp;
        }

        // Swap the current head for the reversed one
        head = curr;
    }
    return head;
};

Approach) Iterative

It first establishes the total length of the LinkedList, and then loops through the initial LinkedList, keeping track of the starting point of the current batch of k nodes, and then reverses them if it reaches k nodes in size.
This process repeats until the loop runs out of elements, by which point we have reversed every batch of k nodes in the LinkedList

Code:

var reverseKGroup = function (head, k) {
    // Count the number of ListNodes
    let n = 0;
    for (let i = head; i != null; n++, i = i.next);

    // Create a dummy LinkedList
    let dummy = new ListNode(0);
    dummy.next = head;

    // Loop through the nodes until we no longer have k or more remaining
    for (let prev = dummy, tail = head; n >= k; n -= k) {
        // Loop through this batch of nodes being reversed
        for (let i = 1; i < k; i++) {
            // Flip the nodes to point in the opposite direction (reverse them)
            let next = tail.next.next;
            tail.next.next = prev.next;
            prev.next = tail.next;
            tail.next = next;
        }

        // Swap the current head for the reversed one
        prev = tail;
        tail = tail.next;
    }
    return dummy.next;
};

Approach) Iterative

This problem is the generalization of the previous problem LeetCode #24 — Swap Nodes In Pairs where we just needed to swap the nodes in pairs. We can also say there we need to reverse the linked lists of size two.

Here, we need to reverse the parts of the linked list of the given size k. Thus, the previous problem is more like a special case of this problem where k = 2.

Here, there are two constraints — one, we cannot change the values in the nodes, and two, we need to do it in constant space.

Idea:
n = a.k + b

Since this problem is the generalization of the previous problem, we can use the ideas discussed there to solve this problem.

This problem is straight-forward as we only have to take parts of the given linked lists of size k, reverse them and join them. The total size n of the given list can be represented as -

This means we need to take a sub-lists (each of size k), reverse them individually, connect them with the next list and in the end, connect all the remaining nodes as is.

Code:

var reverseKGroup = function(head, k) {
    // Base condition
    if (head === null || k === 1) {
        return head;
    }
    // Dummy node before head
    const dummy = new ListNode(-1);
    // Point the next of this dummy to the current head
    dummy.next = head;
    // Node to keep track of the previous node
    let previous = dummy;
    // Variable to keep count of the nodes in the linked list
    let count = 0;
    // Reference to the head which will be used to traverse
    let current = head;
    while (current !== null) {
        count++;
        if (count % k === 0) {
            previous = reverse(previous, current.next);
            current = previous.next;
        } else {
            current = current.next;
        }
    }
    return dummy.next;
};

const reverse = (start, end) => {
    // Previous node of the current node
    let previous = start.next;
    // Current node
    let current = previous.next;
    // Next node of the current node
    let next;
    // Loop for the whole interval
    while (current != end) {
        // Next node of the current node
        next = current.next;
        // Next of current will point to the previous
        current.next = start.next;
        // Current node will become the previous node
        start.next = current;
        // Move pointer ahead
        current = next;
    }
    previous.next = end;
    // Return head node of the reversed linked list
    return previous;
}

Complexity 

Time Complexity

We are taking k nodes at a time and reversing them. In this process, we are going through each node of the linked list only once. Thus, the time complexity will be O(n).

Space Complexity

We are not using any data structure for intermediate computations. Hence, the space complexity will be O(1).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #25. Reverse Nodes in k-Group

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!