## Three List Manipulation Exercises

### October 11, 2016

We must be approaching the middle of the autumn academic term, because the beginning-programmer message boards are starting to fill up with linked-list exercises; one enterprising fellow even sent me an email asking for help on his homework. Here are three tasks that involve manipulating linked lists. We’ve probably done all three before, and they’re simple enough for many of the people that read and respond here, but learners seem to have trouble with them, so we’ll discuss them here:

- Write a function that takes a linked list of integers and returns a new linked list with all the odd integers removed.
- Write a function that removes every
nth item from a linked list.- Write a function that reverses the two halves of a list; if the number of items in the list is odd, the middle element should go with the second half of the list

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

Solution in Common Lisp :

http://pastebin.com/exe9KLP3

I’ve read on pastebin that the free pastebin account is automatically deleted if not used for a certain period of time. So I now use another paste site. See:

http://paste.lisp.org/display/328394

Solution in Ruby

Solution in Scala

“`

val xs= 1 to 20 toList

def drop_odds(list:List[Int])=list.filter(_% 2==0)

def filter_nth(list:List[Int],n:Int)=list.zipWithIndex.filter { case (_, i) => (i + 1) % n != 0 }.map { _._1}

def reverse_two_halves(list:List[Int])=list.splitAt(list.length/2) match{case (left:List[Int],right:List[Int])=>right++left}

println(drop_odds(xs))

println(filter_nth(xs,3))

println(reverse_two_halves(xs))

“`

Run the solution in scala here: http://ideone.com/1R7JMj

Here’s a solution in Java. The removeOddIntegers is a static method because it only works on LinkedLists of integers (whereas the other methods for the problem are class methods that work on LinkedLists of arbitrary type).

Output:

solutions in PHP:

1) without odd integers

function pares($A) {

$l=sizeof($A);

foreach ($A as $a => $v) {

if($v % 20) {

unset($A[$a]);}

}

return print_r($A);

}

2) without Nth element

function elemento($A,$B) {

$n=0;

foreach ($A as $a => $v) {

if(($B-1)==$n) {

unset($A[$a]);

}

$n++;

}

return print_r($A);

}

3) reversed

function rev_halv($A) {

$l=sizeof($A);

if($l % 2==0) {

$m=$l/2;

$odd=false;

}

else {

$m=($l-1)/2;

$odd=true;

}

$ays=array_chunk($A, $m , true);

$m1=array_reverse($ays[0],true);

$m2=array_reverse($ays[1],true);

if($odd) {

$m3=array_reverse($ays[2],true);

$m=$m1+$m3+$m2;

}

else {

$m=$m1+$m2;

}

return print_r($m);

}