Reversing Parts Of A List

December 3, 2013

This exercise is intended for beginning programmers who need to strengthen their understanding of linked lists. It comes in three parts:

First, write a function that reverses the elements of a linked list pairwise; for instance, given the list (1 2 3 4 5 6) the pairwise reversal is (2 1 4 3 6 5). If the list has an odd number of elements, keep the last element at the end of the list; for instance, given the list (1 2 3 4 5) the pairwise reversal is (2 1 4 3 5).

Second, write a function the reverses the elements of a linked list k-wise; for instance, given the list (1 2 3 4 5 6) the 3-wise reversal is (3 2 1 6 5 4) and the 4-wise reversal is (4 3 2 1 6 5).

Third, write a function that reverses the elements of a linked list by halves; for instance, given the list (1 2 3 4 5 6) the half-wise reversal is (3 2 1 6 5 4), with each half reversed independently. If the list has an odd number of elements, the middle element may be assigned to either half at the discretion of the programmer.

Your task is to write the three functions given above. 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

5 Responses to “Reversing Parts Of A List”

  1. Josef Svenningsson said

    Haskell solutions. They’re written in rather different style.

    module Reverse where
    
    reversePairs :: [a] -> [a]
    reversePairs (a:b:as) = b : a : reversePairs as
    reversePairs as       = as
    
    reverseK :: Int -> [a] -> [a]
    reverseK k as = go k [] as
      where go 0 rs as = rs ++ go k [] as
            go n rs (a:as) = go (n-1) (a:rs) as
            go _ rs [] = rs
    
    reverseHalves :: [a] -> [a]
    reverseHalves ls = let (as,bs) = splitAt (length ls `div` 2) ls
                       in reverse as ++ reverse bs
    
  2. Paul said

    In Python.

    from itertools import izip_longest
    
    # FILL for izip_longest - make sure that None can be used in the array
    FILL = object()
    
    def inv_k(arr, k):
        """invert k items"""
        it = iter(arr)
        res = []
        for p in izip_longest(*([it]*k), fillvalue=FILL):
            while p[-1] == FILL:
                p = p[:-1]
            res += reversed(p)
        return res
        
    def inv_pairs(arr):
        return inv_k(arr, 2)
        
    def inv_half(arr):
        return inv_k(arr, (len(arr) + 1) // 2)
    
  3. treeowl said

    Pairwise reversal:

    pairrev (x1:x2:xs) = x2:x1:pairrev xs
    pairrev stub = stub
    
    k-way reversal:
    import Data.List.Split
    krev k = concatMap reverse . splitEvery k
    
    revhalf l = case splitAt (l `quot` 2) l of
      (f, r) -> reverse f ++ reverse r
    
  4. Charlie said

    Would love to hear input on my method. Thanks.

    
    package praxis;
    
    import java.util.LinkedList;
    
    public class Praxis {
    
        public static void main(String[] args) {
            LinkedList<Integer> seq = new LinkedList<Integer>();
            seq.add(1);
            seq.add(2);
            seq.add(3);
            seq.add(4);
            seq.add(5);
            seq.add(6);
            seq.add(7);
            seq.add(8);
            seq.add(9);
            seq.add(10);
            seq.add(11);
            
            int k = 3;
            
            System.out.println(reversal(seq,2));
            System.out.println(reversal(seq,k));
            System.out.println(reversal(seq,seq.size()/2));
        }
        
        public static LinkedList<Integer> reversal(LinkedList<Integer> a,int k) {
            LinkedList<Integer> rev = new LinkedList<Integer>();
            for(int i=0;i<a.size();i=i+k){
                int idx_sec = (i+k-1);
                for(int j=0;j<k;j++){
                    if(idx_sec < a.size()) {
                        rev.add(i+j,a.get(idx_sec-j));
                    }
                    else{
                        if(rev.size() != a.size()){
                            rev.add(i+j,a.get(a.size()-j-1));
                        }
                    }
                }
            }
            return rev;
        }
    }
    

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 615 other followers

%d bloggers like this: