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

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