Reverse Nodes in k-Group

Q: What is the time and space complexity of reversing nodes in k-group?

It runs in O(L) time for a list of L nodes: each node is counted once and flipped once. The in-place version uses O(1) extra memory; copying the values into an array uses O(L).

Q: What happens to the last group if it has fewer than k nodes?

It keeps its original order. Count k nodes before flipping each group; if you reach the end of the list first, leave the rest as it is.

HardLinked list

+10

A singly linked list is stored in two arrays of the same length. Node i holds values[i] and links to node next[i]; -1 ends the list, and the head is node 0. The nodes may be stored in any order, so follow the links, not the array order.

Reverse the list in groups of k nodes: the first k nodes come out reversed, then the next k, and so on. A last group of fewer than k nodes keeps its order. Return the values in the new list order.

Function

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: the index of the node each node links to, or -1 for the last node
valuesinteger-array: the value held by each node
kinteger: the number of nodes in each group to reverse
Returnsinteger-array: the values in the new list order

Constraints

1 ≤ L ≤ 5000, where L is the length of next and of values.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
Each next[i] is -1 or a node index from 0 to L-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Output: [2, 1, 4, 3, 5]
Explanation: The list reads 1, 2, 3, 4, 5 (nodes 0, 2, 4, 1, 3). The pairs 1, 2 and 3, 4 are reversed, and 5 alone is shorter than k = 2, so it stays last.

Input: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Output: [30, 20, 10, 60, 50, 40, 70, 80]
Explanation: The list reads 10, 20, ..., 80. The groups 10, 20, 30 and 40, 50, 60 are reversed. 70, 80 is shorter than k = 3, so it keeps its order.

Input: next = [2, -1, 1]values = [7, 9, 3]k = 3
Output: [9, 3, 7]
Explanation: The array reads 7, 9, 3, but the list reads 7, 3, 9. With k equal to the length, the whole list is one group and comes out reversed: 9, 3, 7.

Follow-up

Can you write it recursively, reversing one group and recursing on the rest of the list? How much extra memory does that use?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Reversing a whole list is one pass of link flips. Here the flips stop every k nodes, and each reversed group must be stitched to the part before it and the nodes after it. You can copy the values into an array and reverse blocks, or relink each group in place with O(1) extra memory.

Copy the values and reverse each block

Intuition

Walk from node 0 with node = next[node] and copy the values into an array in list order. The groups are now the index blocks 0 to k-1, k to 2k-1, and so on: reverse every block that fits whole and leave a shorter last block alone. This takes O(L) time and O(L) extra memory, and it never touches a link.

Algorithm

Walk from node 0 until -1 and append values[node] to an array.
For start = 0, k, 2k, ... while start + k ≤ L: reverse the block from index start to start+k-1.
Leave a shorter block at the end as it is.
Return the array.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

Reverse each group in place by relinking

Intuition

To reverse a whole list you walk it with prev and node and set next[node] = prev. A group is the same loop run k times, with prev starting at after, the node right after the group. The group's first node becomes its last and links to after, so the rest of the list stays attached.

Count k nodes before you flip: if you reach -1 first, the rest is a short group and stays. After the flip, prev is the group's new first node. Link the previous group's last node to it, or make it the head for the first group. The group's old first node is now the last node of the finished part.

Each node is visited twice, once to count and once to flip: O(L) time and a few integers of memory (O(L) in R, which copies the link vector on its first change).

Algorithm

Start with head = 0, prevTail = -1, groupStart = 0.
Walk k steps from groupStart to after; if you reach -1 first, go to step 5.
With prev = after and node = groupStart, repeat k times: save next[node], set next[node] = prev, advance both.
If prevTail is -1, set head = prev; else set next[prevTail] = prev. Set prevTail = groupStart, groupStart = after; go to step 2.
Collect the values from head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pitfalls and edge cases

Reversing the short last group. Count k nodes before flipping; a flipped link cannot be undone without another pass.
Starting the flip with prev = -1, as in a full reversal. A short tail then falls off: the first example returns 2, 1, 4, 3.
Not linking the previous group's last node to the new first node. It still points at the old first node, so k-1 nodes vanish.
Reading the answer from node 0, or reading values left to right. Once a group of k ≥ 2 flips, node 0 is not the head, and the array order was never the list order.
Indexing from 0 in Lua and R, whose arrays start at 1. Keep node indexes 0-based and read next[node + 1].

Frequently asked questions3

What is the time and space complexity of reversing nodes in k-group?

It runs in O(L) time for a list of L nodes: each node is counted once and flipped once. The in-place version uses O(1) extra memory; copying the values into an array uses O(L).

What happens to the last group if it has fewer than k nodes?

It keeps its original order. Count k nodes before flipping each group; if you reach the end of the list first, leave the rest as it is.

Why do solutions to this problem use a dummy node?

With node objects, a dummy node before the head gives the first group a node in front of it, so one line links every group to the finished part. With an array of links, a prevTail that stays -1 until the first group is done does the same job.

def reverseKGroup(next, values, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Expected Output

[2, 1, 4, 3, 5]