Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.

You may not alter the values in the list’s nodes, only nodes itself may be changed.

This problem asks us to reverse a segment of a linked list with k nodes at a time, which is quite similar to a problem we solved before. Recall that we have dealt with a problem that asked us to reverse the sub-list from the mth node and the nth node in a list. And this one is just to do such operation multiple times. We will also introduce both iterative and recursive solutions for this question.

• Iterative Solution

The iterative solution could be confusing because it always needs to manipulate a great number of pointers in this type of problems. However, though the implementation may seem a bit messed up, if we are clear what specific steps that we need to accomplish, then this is actually a straightforward problem.

Very much like that former partial list reversal problem, we need to find the range that we are going to reverse, then reverse the list, and put it back to the correct position. Remember that since we are working on a singly linked list, the four nodes at both sides’ connections are very pivotal. So we always need keep track of those four nodes so that after the reversal, we can splice the reversed sub-list back to the correct place.

So let’s make a list of what we need to do to fully reverse the entire list k nodes at a time:

1. Note that if the subsequent list from head does not contain k nodes, nothing needs to be changed. So we definitely need to check if there are still k nodes left. If there are, we proceed. Otherwise, the algorithm can halt.
2. Reverse the subsequent k consecutive nodes. In the meanwhile, keep track of the information of four nodes, the node before head, head, tail, and the node after tail.
3. At last, put the reversed sub-list back to the correct position, in between the the node before head (former head) and the node after the tail (former tail).
4. Move forward to reverse the next sub-list.

So after we list all the things we need to do, the logic is quite clear, isn’t it? Next, let’s take a look at the implementation.

ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || !head->next || k <= 1) {
        return head;
    }
    
    ListNode dummy(0), *prev = &dummy;
    prev->next = head;
    
    while (true) {
        ListNode* it = prev->next;
        int count = 0;
        while (it) {
            ++count;
            if (count == k) {
                break;
            }
            it = it->next;
        }
        if (count < k) {
            break;
        }
        
        ListNode* nextPrev = prev->next;
        
        ListNode* prev2 = NULL, *cur = prev->next, *next = NULL;
        for (int i = 0; i < k; ++i) {
            next = cur->next;
            cur->next = prev2;
            prev2 = cur;
            cur = next;
        }
        
        prev->next = prev2;
        nextPrev->next = cur;
        
        prev = nextPrev;
    }
    
    return dummy.next;
}

In terms of the implementation, the code is actually not so straightforward as the algorithm. It is mainly because there are a bunch of pointers that we need to reassign and redirect.

At first, as usual, let’s check the corner cases. If the input list is empty or it only contains one element, we definitely need to do nothing on it. Also, if k is less than or equal to 1, the input list does not need to change, either. Next, we use the dummy head trick to make our code simpler. Why does it help in this case? The obvious answer is that the head of the input list may change, and if we keep track of the head while we are running our other logic, the algorithm may become very intractable. Moreover, note that we need to reverse the sub-list that contains head. If we want to reverse a sub-list, those four critical nodes at the connections are very important. If we do not have a dummy node here, our head actually has no precedent node, so our algorithm may become hard to code.

Then, let’s get into the iteration and reverse k nodes at at time. In each iteration, the first thing we need to check is if the list still has at least k subsequent nodes. So a linear scan for at most k nodes is not avoidable. This may seems slightly costly, but we can do a lot more things in this first scan. First, if we find that the traverse reaches the end of the list, we could directly return the current result since no more reversal is needed. Otherwise, we need to keep proceeding. Note that we also need to keep track of those pivotal four connection nodes. Which of them we can already get and store at this moment? Clearly, we can store the precedent node of the head prev and the head node prev->next now. And after the first iteration, we can also get the last two nodes, but in my implementation, I didn’t store them in advance, because in our reversal step, the cur node will reach the successive node of the last node, right? And prev2 is the old tail and the new head. So we don’t necessarily need to store them previously.

Then, we can proceed the reversal. Note that we only need to do k times. So be careful about the condition in the loop. At last, we connect those four connections nodes and goes to the next iteration.

Let’s go through a simple example:

Suppose that we are given a list:
1->2->3->4->5->NULL, k = 2
Initialization:     dummy -> 1, prev = dummy
Current List:       dummy->1->2->3->4->5->NULL
First Iteration:    let it point to 1
                    increase count for 1, becomes 1
                    let it point to 2
                    increase count for 1, becomes 2
                    there are at least 2 nodes left
                    set nextPrev to 1
                    reverse from 1 to 2
                    let 1 point to NULL
                    let 2 point to 1
                    prev2 is 2
                    cur is 3
                    let prev (dummy) point to prev2 (2)
                    let nextPrev (1) point to cur (3)
                    move prev (dummy) to nextPrev (1)
Current List:       dummy->2->1->3->4->5->NULL
Second Iteration:   let it point to 3
                    increase count for 1, becomes 1
                    let it point to 4
                    increase count for 1, becomes 2
                    there are at least 2 nodes left
                    set nextPrev to 3
                    reverse from 3 to 4
                    let 3 point to NULL
                    let 4 point to 3
                    prev2 is 4
                    cur is 5
                    let prev (1) point to prev2 (4)
                    let nextPrev (3) point to cur (5)
                    move prev (1) to nextPrev (3)
Current List:       dummy->2->1->4->3->5->NULL
Second Iteration:   let it point to 5
                    increment count for 1, becomes 1
                    let it point to NULL
                    there is only 1 node left
                    halt
                    
return dummy.next = 2

Time Complexity: O(n) — Basically, we need to iterate the list twice overall. First, in each iteration, we have to first look ahead to check if there are k nodes left. If there are, we need reverse them, which is another linear scan. So the total time complexity is still linear.

Space Complexity: O(1) — The only main data structure we have been using in this implementation are still pointers, so the space cost is constant.

• Recursive Solution

We’ve gone through the iterative solution. Now, it’s turn for the recursion, as well.

Initially, we still need to think about how could we break down the big problem into smaller ones. So in this problem, we are asked to reverse k nodes at a time, so what we are going to do is to reverse first k nodes, then the second set of k nodes and so on, until we reach the end of the list. So in each iteration, we are going to make a k-time reversal and jump to the next round. Thus, if we can do that reversal in the current function call, and then somehow directly obtain a reversed result for the subsequent linked list, and connect them correctly, the problem should be solved. Note that “directly obtain a reversed result for the subsequent linked list” requires us to use the same strategy to reverse a smaller list, so this is the sub-problem that we are looking for.

Next, let’s talk about the specific recursive rule:

1. Base case: The list has less than k nodes.
2. Recursive Rules: 1) Recursively reverse the list beginning from k+1-th node. 2) Reverse the k nodes starting from current head, and connect the new reversed sub-list to the post result.

For the base case, I’d say it’s not that intuitive since so many questions have base cases that could be solved in a constant time. But here, note that to detect if the function call hits the base case or not, it requires at least a scan for k nodes. But we can also do multiple things in this first scan, i.e. get the starting node for the next recursive call, which is supposed to be the k+1-th node.

Next, we can make the next recursive call to reverse the subsequent list, and in the current function, we will do the local reversal and then connect the new reversed list to the post result we obtain from the sub-problem. Then everything is done.

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* it = head;
    int count = 0;
    while (it) {
        ++count;
        if (count == k) {
            break;
        }
        it = it->next;
    }
    if (count < k)
        return head;
    
    ListNode* post = reverseKGroup(it->next, k);
    
    ListNode* prev = NULL, *cur = head, *next = NULL;
    for (int i = 0; i < k; ++i) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    
    head->next = post;
    
    return prev;
}

The structure of the code is quite similar to the iterative solution. We just need to let the subsequent recursive calls to handle all those sub-problems. Our focus in each function call is just to reverse the current k nodes starting from the input head.

Again, let’s try an example:

Suppose that we have an input list:
1->2->3->4->5->NULL, k = 2
Current List:           1->2->3->4->5->NULL
In Main Function:       call reverseKGroup(1)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(1):    let it point to 1
                        increase count for 1, becomes 1
                        let it point to 2
                        increase count for 1, becomes 2
                        there are at least 2 nodes
                        call reverseKGroup(3)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(3):    let it point to 3
                        increase count for 1, becomes 1
                        let it point to 4
                        increase count for 1, becomes 2
                        there are at least 2 nodes
                        call reverseKGroup(5)
Current List:           1->2->3->4->5->NULL
In reverseKGroup(5):    let it point to 5
                        increase count for 1, becomes 1
                        there is only 1 node left
                        hit base case
                        return 5
Current List:           1->2->3->4->5->NULL
In reverseKGroup(3):    get 5 from reverseKGroup(5)
                        
                        reverse from 3 to 4
                        let 3 point to 5
                        return 4
Current List:           1->2->4->3->5->NULL
In reverseKGroup(1):    get 4 from reverseKGroup(3)
                        reverse from 1 to 2
                        
                        let 1 point to 3
                        return 2
Current List:           2->1->4->3->5->NULL
In Main Function:       get 2

Time Complexity: O(n) — Same as the iterative solution. It is because that in each function call, we need to first check if there are k nodes left starting from input head, and if there is, we have to reverse them. So two linear scans are still necessary.

Space Complexity: O(n / k) — With recursion, we need to take the cost of call stacks into consideration. For every k nodes, we are supposed to recursively call the function for once. So the total number of recursive calls is n / k. Within each function, we are still using a couple of pointers only in this algorithm, so they are constant cost. Thus, the total space complexity is O(n / k).