Reversing Parts Of A List

December 3, 2013

For the first exercise, we take the car and cadr of a list, as long as they are not null, write them in reverse order to a result list, and stop at the end, when we reverse the entire list:

(define (rev-2 xs)
  (let loop ((xs xs) (zs (list)))
    (cond ((null? xs) (reverse zs))
          ((null? (cdr xs)) (reverse (cons (car xs) zs)))
          (else (loop (cddr xs) (cons (car xs) (cons (cadr xs) zs)))))))

> (rev-2 '(1 2 3 4 5 6))
(2 1 4 3 6 5)
> (rev-2 '(1 2 3 4 5))
(2 1 4 3 5)

For the second exercise, we make use of the auxiliary functions take and drop from the Standard Prelude to repeatedly collect k elements from the list, append them to a result list, and finally reverse the result; this works properly at the tail end of the list because both take and drop return less than k elements at the end of the list:

(define (rev-k k xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? xs) (reverse zs)
      (loop (drop k xs) (append (take k xs) zs)))))

> (rev-k 3 '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-k 4 '(1 2 3 4 5 6))
(4 3 2 1 6 5)

The third exercise uses Raymond Floyd’s tortoise-and-hare algorithm to race two pointers through the list, one twice as fast as the other; when the hare gets to the end of the list, the tortoise points to the middle of the list. The elements of the first half of the list are collected as the tortoise walks the list; the result is assembled when the hare reaches the end:

(define (rev-half xs)
  (let loop ((t xs) (h xs) (zs (list)))
    (cond ((null? h) (append zs (reverse t)))
          ((null? (cdr h)) (append zs (reverse t)))
          (else (loop (cdr t) (cddr h) (cons (car t) zs))))))

> (rev-half '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-half '(1 2 3 4 5))
(2 1 5 4 3)

You can run the program at http://programmingpraxis.codepad.org/WGr77ExY.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Reversing Parts Of A List”

  1. Josef Svenningsson said
    December 3, 2013 at 10:01 AM

    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
    December 3, 2013 at 10:43 AM

    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)
  4. treeowl said
    December 23, 2013 at 1:34 AM

    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
  5. Charlie said
    December 25, 2013 at 12:42 AM

    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 comment