Reverse Nodes in k-Group

1. Define the problem

Reverse the nodes of a linked list k at a time , and return the list that comes out. Take the first k nodes and flip their order, then the next k nodes, and so on. If fewer than k nodes are left at the end, those nodes are left alone . The function takes a plain array of values plus k, builds the list inside, and returns a plain array. The work splits into two halves: first check that a full group of k nodes really exists, then reverse exactly that stretch and stitch it back between the node before the group and the node after it.

Constraints

The number of nodes is between 0 and 5000
0 ≤ node value ≤ 1000
1 ≤ k ≤ the number of nodes, or larger, in which case nothing changes
Only pointers may be changed; values must not be shuffled around

Example

Inputvalues = [1, 2, 3, 4, 5], k = 2

Output[2, 1, 4, 3, 5]

Explanation The first pair 1, 2 becomes 2, 1 and the second pair 3, 4 becomes 4, 3. Only node 5 is left, which is fewer than k nodes, so it stays where it is.

2. Know the words first

In plain terms

Reversing a stretch: Turning each next pointer inside a run of nodes to aim backwards instead of forwards, so the run reads in the opposite order.
Group previous: The node that sits just in front of the group being reversed. After the flip it must point at what used to be the last node of the group.
Group next: The first node after the group. Reversing stops when it is reached, and it becomes the node the flipped group points at.
Dummy node: A throwaway node placed before the head, so that even the very first group has something in front of it to reattach to.

3. Visualize the solution

Each cell is one slot of the list; the value shows which node is there now

p11

p22

p33

p44

p55

Statusinit

The list is 1 -> 2 -> 3 -> 4 -> 5 and groups of k = 2 will be flipped.

What happens in this step

list = 1 -> 2 -> 3 -> 4 -> 5
k = 2
groupPrev = the dummy node sitting in front of the head

The first group is the pair 1, 2.

Step 1 of 7

Steps to visualize

Read the row left to right as the list in its current order.
The frame marks the group of k nodes being worked on.
Before reversing, count k steps forward to check a full group exists.
Reverse that group, then reattach it between the node before it and the node after it.
When a count runs off the end, the leftover nodes are left untouched and the walk ends.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell is one slot of the list; the value shows which node is there now

p11

p22

p33

p44

p55

Statusinit

The list is 1 -> 2 -> 3 -> 4 -> 5 and groups of k = 2 will be flipped.

What happens in this step

list = 1 -> 2 -> 3 -> 4 -> 5
k = 2
groupPrev = the dummy node sitting in front of the head

The first group is the pair 1, 2.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function toList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = new ListNode(values[i], head);
  }
  return head;
}

function toArray(head) {
  const out = [];
  for (let node = head; node !== null; node = node.next) {
    out.push(node.val);
  }
  return out;
}

function reverseKGroup(values, k) {
  const head = toList(values);
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth !== null; i++) {
      kth = kth.next;
    }
    if (kth === null) {
      break;
    }

    const groupNext = kth.next;
    let prev = groupNext;
    let current = groupPrev.next;

    while (current !== groupNext) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    const newGroupPrev = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = newGroupPrev;
  }

  return toArray(dummy.next);
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 2, 3, 4, 5], k = 2`	`[2, 1, 4, 3, 5]`	example from the description, with a leftover node
`values = [1, 2, 3, 4, 5], k = 3`	`[3, 2, 1, 4, 5]`	one full group and a short leftover group
`values = [1, 2, 3], k = 1`	`[1, 2, 3]`	groups of one, which must leave the list unchanged
`values = [1, 2], k = 3`	`[1, 2]`	no full group exists at all
`values = [], k = 2`	`[]`	empty list, nothing to reverse
`values = [1, 2, 3, 4, 5, 6], k = 3`	`[3, 2, 1, 6, 5, 4]`	a longer list that divides into full groups with nothing left over

Reverse Nodes in k-Group