## 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

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

public class Praxis {

public static void main(String[] args) {

int k = 3;

System.out.println(reversal(seq,2));
System.out.println(reversal(seq,k));
System.out.println(reversal(seq,seq.size()/2));
}

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()) {