## Reverse Every K Nodes Of A Linked List

### August 26, 2011

Here is another from our collection of interview questions:

Given a list of elements and a block size k, return the list of elements with every block of k elements reversed, starting from the beginning of the list. For instance, given the list 1, 2, 3, 4, 5, 6 and the block size 2, the result is 2, 1, 4, 3, 6, 5.

Your task is to write a function to solve the sublist-reversal problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 27 Responses to “Reverse Every K Nodes Of A Linked List”

1. uberlazy said

In Clojure.

```(defn rev [n xs]
(mapcat reverse
(partition-all n xs)))
```
2. Tante Hedwig said

import Data.List

revBlockwise n = concat
. unfoldr (\e -> case e of [] -> Nothing;x -> Just (reverse \$ take n x,drop n x))

3. Here’s my clojure solution. More details at my blog.

```;;Reverse k nodes

(def linked-list (java.util.LinkedList. [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]))

(defn reverse-sub-lists [l k]
(map reverse (partition-all k l)))
```
4. Oops, posted the wrong version:

```;;Reverse k nodes

(def linked-list (java.util.LinkedList. [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]))

(defn reverse-sub-lists [l k]
(mapcat reverse (partition-all k l)))
```
5. Joseph said

Python (please post a more elegant solution):

```def rev_groups(inp_list, n):
lists = [inp_list[i:i+n] for i in range(0, len(inp_list), n)]
for lis in lists:
lis.reverse()
return lists
```
6. Using PLT Racket

```(define (reverse-k lyst k)
(if (> k (length lyst))
lyst
(let*-values (((front rear) (split-at lyst k)))
(append (reverse front)
(reverse-k rear k)))))
```

Essentially the same as the take/drop version given except that split-at does both at the same time. I had to check against length instead of null? because split-at complained when given a list shorter than k.

7. Oops. I forgot to change let*-values back to let-values.

8. C++

```#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

template<class BiIter, class OutIter>
void reverse_k(int k, BiIter first, BiIter last, OutIter result)
{
BiIter end(first);
do {
BiIter current(end);
int d(std::distance(current, last));
else end = last;
std::reverse_copy(current, end, result);
} while(end != last);
}

int main(int argc, char** argv)
{
std::list<int> list;
for(int i = 1; i <= 6; ++i) list.push_back(i);
std::ostream_iterator<int> out(std::cout, ", ");

for(int i = 1; i <= 6; ++i) {
reverse_k(i, list.begin(), list.end(), out);
std::cout << std::endl;
}
}
```
9. Been playing with Haskell while waiting for C++ code to compile. Here is a solution I came up with.

sublists k [] = []
sublists k l = take k l : sublists k (drop k l)

reverseSublists k l = map reverse \$ sublists k l

10. uberlazy said

Everyone’s doing Haskell today. Here’s my take:

rev _ [] = []
rev chunkSize xs = reverse chunk ++ rev chunkSize rest where (chunk, rest) = splitAt chunkSize xs

11. Bostan Fericit said

Solution in Java.

public static void reverseNodes(int blockSize, List list) {
int end;
char c;

for(int i = 0, start = 0; i list.size()) ? list.size() : i + blockSize) – 1;

while(start < end) {
c = list.get(start);
list.set(start++, list.get(end));
list.set(end–, c);
}

}
}

12. Mike said

Two Python 3 solutions. One returns a new list, the other reverses the groups in-place.

The problem doesn’t specify what to do when the number of elements in the list is not a multiple of the group size. For example,

rev_groups([1,2,3,4,5], 3) -> ?

I chose to reverse the short group.

```
def rev_groups(s,k):
ans = []
for b in range(0, len(s) + k + 1, k):
ans.extend(reversed(s[b:b+k]))
return ans

def rev_groups_inplace(s,k):
for b in range(0, len(s) + k + 1, k):
s[b:b+k] = reversed(s[b:b+k])

```
13. slabounty said

A ruby version (could not for the life of me find a one liner but would love to see one) …

```a = %w[a b c d e f]
b = []
a.each_slice(2) { |d| d.reverse.each {|c| b<<c} }
p b
```
14. Paul Mylchreest said

# Ruby version

def reverse list, k
list.each_slice(k).collect{ |s| s.reverse }.flatten
end

reverse [1, 2, 3, 4, 5, 6], 2

15. slabounty said

That’s what I was looking for @Paul Mylchreest. Well done.

```function chunked_reverse(array \$arr, \$chunk_size){
return call_user_func_array('array_merge', array_map(function(\$chunk_arr){return array_reverse(\$chunk_arr);}, array_chunk(\$arr, \$chunk_size)));
}
```
17. fengshaun said

``` reverseNodes :: Int -> [a] -> [a] reverseNodes _ [] = [] reverseNodes n xs = (reverse \$ take n xs) ++ reverseNodes n (drop n xs) ```

18. mrjbq7 said

```: reverse-nodes ( seq -- seq' )
2 group [ reverse ] map concat ;
```

And, to use it:

```( scratchpad ) "abcdefg" reverse-nodes .
```
19. JavaScript using nodejs:

``` /** * Program that solve the sublist-reversal problem. * * @see https://programmingpraxis.com/2011/08/26/reverse-every-k-nodes-of-a-linked-list/ */ var App = function() {```

``` /** * Reverse every sub-list from a given list. * @param list A list of integers. * @param size The size of the sub-list. */ this.reverse = function(list, size) { // Validate input. if (!list || !size || size <= 0) { throw 'Illegal arguments'; } var result = []; for (var i = 0; i < list.length; i += size) { var sub = list.slice(i, i + size).reverse(); for (var j = 0; j < sub.length; j++) { result.push(sub[j]); } } return result; }; }; // Test. var list = [1,2,3,4,5,6,7,8,9]; var size = 2; var a = new App(); var result = a.reverse(list, size); ```

```console.log(result); ```

20. JavaScript using nodejs:

``````
/**
* Program that solve the sublist-reversal problem.
*
*/
var App = function() {

/**
* Reverse every sub-list from a given list.
* @param list A list of integers.
* @param size The size of the sub-list.
*/
this.reverse = function(list, size) {

// Validate input.
if (!list || !size || size <= 0) {
throw 'Illegal arguments';
}

var result = [];

for (var i = 0; i < list.length; i += size) {
var sub = list.slice(i, i + size).reverse();
for (var j = 0; j < sub.length; j++) {
result.push(sub[j]);
}
}

return result;
};
};

// Test.

var list = [1,2,3,4,5,6,7,8,9];
var size = 2;
var a = new App();
var result = a.reverse(list, size);

console.log(result);
``````
21. Axio said

```f i [] = []
f i l = reverse hd ++ f i tl where (hd,tl)=splitAt i l
```
22. catalinc said

Go:

```package main

import "fmt"

func kreverse(a []int, k int) {
start := 0
end := 0
for start  len(a) {
end = len(a)
}
i := start
j := end - 1
for i < j {
a[i], a[j] = a[j], a[i]
i++
j--
}
start = end
}
}

func main() {
a := []int{1, 2, 3, 4, 5, 6}
kreverse(a, 4)
fmt.Printf("%v\n", a)
}
```
23. fa said

mm.. some are preceeding ^^

KRev.java

``` 1 import java.util.List;
2 import java.util.Arrays;
3 import java.util.Collections;
4
5 public class KRev
6 {
7     public static <T> void kRev(List<T> aList, int aBlockSize) {
8         int i;
9
10         for (i = aBlockSize; i < aList.size(); i += aBlockSize)
11             Collections.reverse(aList.subList(i - aBlockSize, i));
12         Collections.reverse(aList.subList(i - aBlockSize, aList.size()));
13     }
14
15     public static void main(String args[]) {
16         List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
17         System.out.println(list); kRev(list, 3); System.out.println(list);
18     }
19 }
20
```

revk.go

``` 1 package main
2 import "fmt"
3
4 func revK(sl []int, bs int) {
5     reverse := func (sl []int) {
6         for i, j := 0, len(sl)-1; i < j; i, j = i+1, j-1 {
7             sl[i], sl[j] = sl[j], sl[i]
8         }
9     }
10     var i int
11     for i = bs; i < len(sl); i += bs { reverse(sl[i - bs : i]) }
12     reverse(sl[i - bs : len(sl)])
13 }
14
15 func main() {
16     print := func (sl []int) {
17         for _, i := range sl { fmt.Printf("%d\t", i) }
18         fmt.Printf("\n")
19     }
20     sl := []int{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
21     print(sl); revK(sl, 7); print(sl)
22 }
23
```
24. Mike said

Here’s a Python 3 version that works for any iterable. It is a generator that lazily evaluates groups of k items from the input iterable and yields the items in reverse order. The null argument should be set to a value that cannot appear in the input, and defaults to None.

```from itertools import zip_longest

def rev_group_gen(seq, k, null=None):
for group in zip_longest(*([iter(seq)]*k), fillvalue=null):
for x in reversed(group):
if x != null:
yield x

# test
from itertools import count, islice

list(islice(rev_group_gen(count(),3), 100, 110))
#  output -> [100, 99, 104, 103, 102, 107, 106, 105, 110, 109]

```

Someone requested some one-liners.

Here a a couple in Python 3:

```from itertools import zip_longest

s = range(10)
k = 3

# for any iterable
rg1 = [x for g in zip_longest(*([iter(s)]*k)) for x in reversed(g) if x is not None]

# for sequence types (list, tuple, string, ...)
rg2 = sum((list(reversed(s[g:g+k])) for g in range(0,len(s),k)),[])

```
25. Matthew Pickering said

One line in python –
for y in [x[n:n+2] for n in range(0,len(x),2)]],[])

26. Matthew Pickering said

One line in python

```def revk(x):return sum([y[::-1] for y in [x[n:n+2] for n in range(0,len(x),2)]],[])
```
27. brooknovak said

Solution in C# for a singly linked list. Uses O(k) auxiliary space.

```public void ReverseBlocks(int k) {
if (k <= 0)
throw new ArgumentOutOfRangeException ("k");
if (head == null || k == 1)
return;

Node[] block = new Node[k];
tail = null;
int i = 0;
while (current != null) {
block [i] = current;
next = current.Next;
i++;
if (i == k || current.Next == null) {
for(int j = i - 1; j > 0; j--)
block [j].Next = block [j - 1];