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
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;
    // Collect all nodes
    ArrayList<Node> nodes = new ArrayList<>();
    while (cur != null) {
        nodes.add(cur);
        cur = cur.next;
    }

    // Chunk by chunk iteraiton
    for (int i=0; i+n<=nodes.size(); i+=n) {
        // Reverse every chunk
        Collections.reverse(nodes.subList(i, i+n));
    }

    // Rewire each node
    cur = list.sentinel;
    for (Node node : nodes) {
        cur.next = node;
        cur = node;
    }
    cur.next = null;
}

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

    Node prev_chunk_tail = list.sentinel;

    while (true) {
        Node chunk_tail = prev_chunk_tail;
        for (int i=0; i<n && chunk_tail!=null; ++i) {
            chunk_tail = chunk_tail.next;
        }

        if (chunk_tail == null) {
            return;
        }

        Node chunk_head = prev_chunk_tail.next;
        Node next_chunk_head = chunk_tail.next;

        Node prev = next_chunk_head;
        Node cur = chunk_head;
        for (int i=0; i<n; ++i) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        prev_chunk_tail.next = chunk_tail;
        prev_chunk_tail = chunk_head;
    }
}

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
package main

import (
	"fmt"
	"math/rand"
)

type Node[E comparable] struct {
	elem E
	next *Node[E]
}

type List[E comparable] struct {
	sentinel Node[E]
}

func (l *List[E]) print() {
	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[E]) reverse_every_n_chunk_naive(n int) {
	if n <= 1 {
		return
	}

	// Collect all nodes
	nodes := []*Node[E]{}
	{
		cur_node := l.sentinel.next
		for cur_node != nil {
			nodes = append(nodes, cur_node)
			cur_node = cur_node.next
		}
	}

	// Chunk by chunk iteration
	for i := 0; i+n <= len(nodes); i += n {
		for left, right := i, i+n-1; left < right; left, right = left+1, right-1 {
			// Swap
			nodes[left], nodes[right] = nodes[right], nodes[left]
		}
	}

	// Rewire the passed in List
	prev_node := &l.sentinel
	for _, v := range nodes {
		prev_node.next = v
		prev_node = v
	}
	// final node
	prev_node.next = nil
}

func (l *List[E]) reverse_every_n_chunk(n int) {
	if n <= 1 {
		return
	}

	prev_chunk_tail := &l.sentinel
	for {
		chunk_head := prev_chunk_tail.next

		chunk_tail := chunk_head
		for i := 1; i < n && chunk_tail != nil; i++ {
			chunk_tail = chunk_tail.next
		}

		// End of list
		if chunk_tail == nil {
			return
		}

		prev_node := chunk_tail.next
		cur_node := chunk_head
		for i := 0; i < n; i++ {
			tmp := cur_node.next
			cur_node.next = prev_node
			prev_node = cur_node
			cur_node = tmp
		}

		prev_chunk_tail.next = chunk_tail
		prev_chunk_tail = chunk_head
	}
}

func is_list_eq[E comparable](a *List[E], b *List[E]) bool {
	a_cur := a.sentinel.next
	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[E]) clone() List[E] {
	result := List[E]{}
	input_cur := l.sentinel.next
	out_cur := &result.sentinel
	for input_cur != nil {
		out_cur.next = &Node[E]{elem: input_cur.elem}
		out_cur = out_cur.next

		input_cur = input_cur.next
	}
	return result
}

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

func qcheck(loop int) {
	for range loop {
		slice := rand.Perm(200)
		n := rand.Intn(len(slice) + 2)
		list := list_from_slice(slice)

		x_list := list.clone()
		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)
}