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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
class Node {
    public int elem;
    public Node next;
}

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

void reverse_every_n_chunk_naive(List list, int n) {
    if (n <= 1) {
        return;
    }

    Node cur = list.sentinel.next;
    ArrayList<Integer> array_list = new ArrayList<>();
    while (cur != null) {
        array_list.add(cur.elem);
        cur = cur.next;
    }

    for (int i=0; i<array_list.size(); ++i) {
        if ((i+1)%n == 0) {
            java.util.List<Integer> chunk = array_list.subList(i-(n-1), i+1);
            var reversed_chunk = java.util.List.copyOf(chunk.reversed());
            for (int j=0; j<n; ++j) {
                array_list.set(i-(n-1)+j, reversed_chunk.get(j));
            }
        }
    }

    // overwrite list
    cur = list.sentinel;
    for (int i=0; i<array_list.size(); ++i) {
        var node = new Node();
        node.elem = array_list.get(i);
        cur.next = node;
        cur = node;
    }
}

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

    Node final_in_prev_chunk = list.sentinel;
    Node cur = list.sentinel.next;
    for (int step=1; cur!=null; step++) {
        final Node next = cur.next;
        if (step % n == 0) {
            // start of inner iteration
            final Node first = final_in_prev_chunk.next;
            final_in_prev_chunk.next = cur;

            // Pretend prev is the beginning of next chunk
            Node prev = next;
            Node inner_cur = first;

            for (var j=1; j<=n; ++j) {
                var next_node = inner_cur.next;
                inner_cur.next = prev;

                // advance
                prev = inner_cur;
                inner_cur = next_node;
            }

            // after reversing, first becomes final
            final_in_prev_chunk = first;
        }
        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");
}

List from_array(int[] array) {
    List l = new List(null);
    Node cur = l.sentinel;
    for (int i=0; i<array.length; ++i) {
        var node = new Node();
        node.elem = array[i];
        cur.next = node;
        cur = node;
    }
    return l;
}

boolean is_list_eq(List x, List y) {
    var cur_x = x.sentinel.next;
    var cur_y = y.sentinel.next;
    while (true) {
        if (cur_x == null && cur_y == null) {
            return true;
        }
        if (cur_x == null && cur_y != null) {
            return false;
        }
        if (cur_x != null && cur_y == null) {
            return false;
        }
        if (cur_x.elem != cur_y.elem) {
            return false;
        }
        cur_x = cur_x.next;
        cur_y = cur_y.next;
    }
}

void qcheck(int loop) {
    Random r = new Random();
    for (var l=0; l<loop; ++l) {
        int len = r.nextInt(100);
        int n = r.nextInt(len+2);
        int[] array = new int[len];
        for (var i = 0; i < array.length; ++i) {
            array[i] = i + 1;
        }
        List o_list = from_array(array);
        List x_list = from_array(array);
        List y_list = from_array(array);

        reverse_every_n_chunk_naive(x_list, n);
        reverse_every_n_chunk(y_list, n);
        if (!is_list_eq(x_list, y_list)) {
            print_list(o_list);
            print_list(x_list);
            print_list(y_list);
            System.exit(-1);
        }
    }
    System.out.println("Loop " + loop + " OK");
}

void main() {
    qcheck(1000);
}
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
package main

import (
	"fmt"
	"math/rand"
)

type Node struct {
	elem int
	next *Node
}

type List struct {
	sentinel Node
}

func (l *List) print() {
	var cur_node = l.sentinel.next
	fmt.Print("List: ")
	for cur_node != nil {
		fmt.Print("", cur_node.elem, "->")
		cur_node = cur_node.next
	}
	fmt.Println()
}

func (l *List) reverse_every_n_chunk_naive(n int) {
	if n <= 1 {
		return
	}
	if l.sentinel.next == nil {
		// Empty list
		return
	}

	var num_elems = 0
	{
		var cur_node = l.sentinel.next
		for cur_node != nil {
			num_elems++
			cur_node = cur_node.next
		}
	}

	var slice = make([]int, num_elems)
	{
		var cur_node = l.sentinel.next
		var i = 0
		for cur_node != nil {
			slice[i] = cur_node.elem
			cur_node = cur_node.next
			i++
		}
	}

	for i := 0; i < num_elems; i++ {
		if (i+1)%n == 0 {
			// reverse the last n elems
			for j := 1; j <= n/2; j++ {
				// swap pairs, e.g. i-(n-1) and i-0
				var x = i - (j - 1)
				var y = i - (n - 1) + (j - 1)
				slice[x], slice[y] = slice[y], slice[x]
			}
		}
	}

	// Rewire the passed in List
	var cur_node = &l.sentinel
	for _, v := range slice {
		cur_node.next = &Node{elem: v}
		cur_node = cur_node.next
	}
}

func (l *List) reverse_every_n_chunk(n int) {
	if n <= 1 {
		return
	}
	var final_node_in_prev_chunk = &l.sentinel

	var cur = l.sentinel.next
	for i := 0; cur != nil; i++ {
		var next = cur.next
		if (i+1)%n == 0 {
			// cur is the end of current chunk

			// Nested loop for nodes inside current chunk
			// [first, cur]
			var first = final_node_in_prev_chunk.next

			// Pretend prev is start of next chunk
			var prev = next
			var nested_cur = first
			for j:=1; j<=n; j++ {
				var next_node = nested_cur.next
				nested_cur.next = prev

				// advance
				prev = nested_cur
				nested_cur = next_node
			}

			// After reverse: [cur, first]
			final_node_in_prev_chunk.next = cur
			final_node_in_prev_chunk = first
		}
		cur = next
	}
}

func is_list_eq(a *List, b *List) bool {
	var a_cur = a.sentinel.next
	var b_cur = b.sentinel.next
	for {
		if a_cur == nil && b_cur == nil {
			return true
		}
		if a_cur == nil && b_cur != nil {
			return false
		}
		if a_cur != nil && b_cur == nil {
			return false
		}
		if a_cur.elem != b_cur.elem {
			return false
		}
		a_cur = a_cur.next
		b_cur = b_cur.next
	}
}

func (l *List) clone() List {
	var result = List{}
	var input_cur = l.sentinel.next
	var out_cur = &result.sentinel
	for input_cur != nil {
		out_cur.next = &Node{elem: input_cur.elem}
		out_cur = out_cur.next

		input_cur = input_cur.next
	}
	return result
}

func list_from_slice(slice []int) List {
	var result = List{}
	var cur = &result.sentinel
	for _, v := range slice {
		cur.next = &Node{elem: v}
		cur = cur.next
	}
	return result
}

func qcheck(loop int) {
	for range loop {
		var slice = make([]int, 100)
		var n = rand.Intn(len(slice) + 2)
		for i := range slice {
			slice[i] = i + 1
		}
		var list = list_from_slice(slice)

		var x_list = list.clone()
		var y_list = list.clone()

		x_list.reverse_every_n_chunk_naive(n)
		y_list.reverse_every_n_chunk(n)
		if !is_list_eq(&x_list, &y_list) {
			fmt.Println(n)
			list.print()
			x_list.print()
			y_list.print()
			panic("Wrong test")
		}
	}
	fmt.Println("Loop", loop, "OK")
}

func main() {
	qcheck(1000)
}