Reverse Nodes In K Group

The problem

You are given head, the first node of a linked list, and a number k. A node holds a value, val, and a link, next, to the node after it, and the last node's next is null. Starting from the first node, take the nodes in groups of k and reverse the order of the nodes inside each group. If fewer than k nodes are left at the end, leave them as they are. Return the first node of the changed list. Move the nodes by changing their links, not the values they hold. With k = 1 each group is one node, so the list stays as it is.

What to write

type ListNode = {val:number;next:ListNode|null};

function solve(head: ListNode | null, k: number): ListNode | null

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}
k = 2

Output
{"val":2,"next":{"val":1,"next":{"val":4,"next":{"val":3,"next":{"val":5,"next":null}}}}}

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}
k = 3

Output
{"val":3,"next":{"val":2,"next":{"val":1,"next":{"val":4,"next":{"val":5,"next":null}}}}}

Constraints

Change links rather than node values; 1 ≤ k ≤ list length.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Only complete groups are reversed, and you cannot know that a group is complete before you have counted k nodes. So count first and change links afterwards. Notice also that the list links forward only: once a group's links are turned, the node after the group can be reached only if you kept hold of it.

2. Hint 2: Ask a smaller question

   The answer for 1 → 2 → 3 → 4 → 5 with k = 2 is 2 → 1 → 4 → 3 → 5. Look at node 1. Which node does it link to in the answer? Is that node known at the moment the first group has been reversed, or only later?

3. Hint 3: Name the pattern

   No value moves. Every node keeps its value and only the links change, which is linked list pointer rewiring: the same nodes in a new order. Reverse each group the way you reverse a whole list, then repair its two joins: the node before the group, and the group's old first node, which is now its last. Read the lesson on linked list pointer rewiring.

4. Hint 4: State the invariant

   Before each group is handled, everything up to one known node, the node before the group, is already in its final order, and that node still links to the untouched rest of the list. Handling a group moves this boundary forward by k nodes, or ends the work if fewer than k remain.

5. Hint 5: Sketch the pseudocode

   The anchor starts as an extra node placed before head. Repeat: walk k nodes from the anchor to the group's last node, or stop if the list ends. Reverse the group's links; its first node points past the group. Link the anchor to that last node. The group's old first node becomes the anchor. Return the extra node's next node.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Check that a full group exists before reversing links. Connect each reversed group to the untouched suffix.

The slow way

Copy the values into an array, reverse every full block of k values there, and write them back into the nodes. The result looks right, but it needs O(n) extra memory, and it changes the values stored in the nodes, where the task asks you to change only the links.

The insight

Reversing one group is the reversal of a whole list, stopped after k nodes. What is new are the two joins of a group: the node before the group must end up pointing to the group's last node, and the group's first node to whatever follows the group. If the reversal starts with the node after the group as the previous node, it makes the second join itself.

Step by step

1. Put a placeholder before the head: the node before the first group. The first group has no node before it. A placeholder, an extra node that is not part of the answer, gives it one. Then every group is handled the same way.
2. Count k nodes ahead to find the last node of the next group. Links may be changed only once a full group is known to exist. The walk also finds the group's last node, which will be its first.
3. Fewer than k nodes are left: stop and leave them as they are. A short last group keeps its original order. None of its links has been touched, because the counting comes before any link is changed.
4. Reverse the group's links, with its first node pointing past the group. This is the reversal of a whole list with one change: the previous node starts as the node after the group, not as null. So the group's first node, which ends up last, links to the rest of the list.
5. Link the node before the group to the group's new first node. The node before the group still points to the group's old first node, which is now its last. Until this link is set, the other nodes of the group cannot be reached from the front.
6. The group's old first node is now the node before the next group. The next group starts right after this group's last node, and that is the node the reversal began with. That node was saved before the links changed.
7. The answer starts right after the placeholder. The answer may start at a different node than head: the first group's last node comes first now. The placeholder has pointed to that node since the first group was linked in.

The same numbered steps are the comments in each solution.

function solve(head, k) {
  // 1. Put a placeholder before the head: the node before the first group
  const dummy = { val: 0, next: head };
  let before = dummy;
  while (true) {
    // 2. Count k nodes ahead to find the last node of the next group
    let end = before;
    for (let i = 0; i < k && end; i++) end = end.next;
    // 3. Fewer than k nodes are left: stop and leave them as they are
    if (!end) break;
    // 4. Reverse the group's links, with its first node pointing past the group
    const after = end.next;
    let prev = after,
      cur = before.next;
    const first = cur;
    while (cur !== after) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    // 5. Link the node before the group to the group's new first node
    before.next = end;
    // 6. The group's old first node is now the node before the next group
    before = first;
  }
  // 7. The answer starts right after the placeholder
  return dummy.next;
}

type ListNode = { val: number; next: ListNode | null };
function solve(head: ListNode | null, k: number): ListNode | null {
  // 1. Put a placeholder before the head: the node before the first group
  const dummy: ListNode = { val: 0, next: head };
  let before = dummy;
  while (true) {
    // 2. Count k nodes ahead to find the last node of the next group
    let end: ListNode | null = before;
    for (let i = 0; i < k && end; i++) end = end.next;
    // 3. Fewer than k nodes are left: stop and leave them as they are
    if (!end) break;
    // 4. Reverse the group's links, with its first node pointing past the group
    const after: ListNode | null = end.next;
    let prev: ListNode | null = after,
      cur: ListNode | null = before.next;
    const first = cur!;
    while (cur !== after) {
      const next: ListNode | null = cur!.next;
      cur!.next = prev;
      prev = cur;
      cur = next;
    }
    // 5. Link the node before the group to the group's new first node
    before.next = end;
    // 6. The group's old first node is now the node before the next group
    before = first;
  }
  // 7. The answer starts right after the placeholder
  return dummy.next;
}

def solve(head, k):
    # 1. Put a placeholder before the head: the node before the first group
    dummy = ListNode(0, head)
    before = dummy
    while True:
        # 2. Count k nodes ahead to find the last node of the next group
        end = before
        for _ in range(k):
            if not end:
                break
            end = end.next
        # 3. Fewer than k nodes are left: stop and leave them as they are
        if not end:
            break
        # 4. Reverse the group's links, with its first node pointing past the group
        after = end.next
        prev, cur = after, before.next
        first = cur
        while cur is not after:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        # 5. Link the node before the group to the group's new first node
        before.next = end
        # 6. The group's old first node is now the node before the next group
        before = first
    # 7. The answer starts right after the placeholder
    return dummy.next

Example 1, traced

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}
k = 2

Output
{"val":2,"next":{"val":1,"next":{"val":4,"next":{"val":3,"next":{"val":5,"next":null}}}}}

Why it works

Before each group, everything up to the node before the group is in its final order, and that node links to the untouched rest. Reversing a full group and repairing its two joins puts k more nodes in final order and moves that boundary past them. When fewer than k nodes are left, they are already where they belong.

Time and space

Time O(n), extra space O(1). Each node is visited at most twice: once when its group is counted and once when its link is turned. So the time is O(n). The method keeps a placeholder and a few pointers whatever the length of the list: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Start the reversal with the node after the group as the previous node. Starting from null, as when reversing a whole list, cuts the list after the group: the first example returns 2 → 1.
• Link the node before the group to the group's new first node. Without that link the first example returns 1 → 3 → 5, because nodes 2 and 4 cannot be reached from the front.
• Count the k nodes before changing any link. If a short last group is reversed like the others, the second example ends in 5 → 4 instead of 4 → 5.

Pattern

Linked list pointer rewiring. Builds on Reverse Linked List and Remove Nth Node From End of List.

Keep going