Small quiz:

Given a singly linked list and an integer n, the goal is to reverse the nodes of the list in groups of n.

Example:

1
2
3
4
5
Input:
    1->2->3->4->5->6->7->8->null
    n = 3
Output:
    3->2->1->6->5->4->7->8->null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Node {
  public int elem;
  public Node next;
}

class List {
  Node sentinel;
  public List(Node first) {
    sentinel = new Node();
    sentinel.next = first;
  }
}

// reverse [from, to)
void reverse(Node prev, Node from, Node to) {
  for (Node cur = from; cur != to; /* empty */) {
    Node tmp = cur.next;
    cur.next = prev;

    prev = cur;
    // Move on to next
    cur = tmp;
  }
}

void reverse_every_n_chunk(List list, int n) {
  if (n <= 0) {
    return;
  }

  Node final_in_prev_chunk = list.sentinel;
  Node cur = list.sentinel.next;
  int step = 1;
  while (cur != null) {
    final Node next = cur.next;
    if (step == n) {
      // start of inner iteration
      Node first_in_chunk = final_in_prev_chunk.next;
      final_in_prev_chunk.next = cur;

      // Pretend prev is next (beginning of next chunk)
      Node prev = next;
      // right end is exclusive
      reverse(prev, first_in_chunk, next);

      // after reversing first becomes final
      final_in_prev_chunk = first_in_chunk;
      // reset step
      step = 1;
    } else {
      step++;
    }
    cur = next;
  }
}

void print_list(List list) {
  Node cur = list.sentinel.next;
  while (cur != null) {
    IO.print(cur.elem);
    IO.print("->");
    cur = cur.next;
  }
  IO.println("null");
}

void main() {
  int num = 8;
  Node[] nodes = new Node[num];
  for (var i=1; i<=num; ++i) {
    var node = new Node();
    node.elem = i;
    nodes[i-1] = node;
  }

  for (var i=0; i<num-1; ++i) {
    nodes[i].next = nodes[i+1];
  }
  nodes[num-1].next = null;

  List list = new List(nodes[0]);

  print_list(list);

  reverse_every_n_chunk(list, 3);

  print_list(list);
}