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.
Programming Praxis 
In Clojure.
In Haskell:
import Data.List
revBlockwise n = concat
. unfoldr (\e -> case e of [] -> Nothing;x -> Just (reverse $ take n x,drop n x))
Here’s my clojure solution. More details at my blog.
Oops, posted the wrong version:
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 listsUsing 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.
Oops. I forgot to change let*-values back to let-values.
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)); if(d >= k) std::advance(end, k); 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; } }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
Everyone’s doing Haskell today. Here’s my take:
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);
}
}
}
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])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# Ruby version
def reverse list, k
list.each_slice(k).collect{ |s| s.reverse }.flatten
end
reverse [1, 2, 3, 4, 5, 6], 2
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))); }So many haskells!
reverseNodes :: Int -> [a] -> [a]
reverseNodes _ [] = []
reverseNodes n xs = (reverse $ take n xs) ++ reverseNodes n (drop n xs)
How about a Factor!
: reverse-nodes ( seq -- seq' ) 2 group [ reverse ] map concat ;And, to use it:
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);
JavaScript using nodejs:
Haskell
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) }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 } 20revk.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 } 23Here’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:
One line in python –
for y in [x[n:n+2] for n in range(0,len(x),2)]],[])
One line in python
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 current = head, next; Node[] block = new Node[k]; head = null; 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]; if (head == null) head = block [i - 1]; else tail.Next = block [i - 1]; tail = block [0]; i = 0; } current = next; } tail.Next = null; }