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.

About these ads

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

    In Haskell:

    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));
                    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;
            }
    }
    
  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.

  16. adam said
    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

    So many haskells!


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

  18. mrjbq7 said

    How about a Factor!

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

    And, to use it:

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


    /**
    * Program that solve the sublist-reversal problem.
    *
    * @see http://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.
     * 
     * @see http://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);
    
  21. Axio said

    Haskell

    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 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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 636 other followers

%d bloggers like this: