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.
Programming Praxis 
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
def drop_odds(list) list.reject(&:odd?) end def remove_every_nth_item(n, list) list.each_slice(n).map { |l| l.take(n-1) }.flatten end def reverse_two_halves(list) n = list.size / 2 [list.take(n), list.drop(n)].reverse.flatten endSolution 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).
public class LinkedList<T> { public static class Node<T> { T data; Node<T> next = null; } Node<T> head; // Adds an element to the front of a LinkedList. public void add(T element) { Node<T> node = new Node<T>(); node.data = element; node.next = head; head = node; } @Override public String toString() { StringBuffer output = new StringBuffer("["); Node<T> current = head; while (current != null) { if (current != head) output.append(", "); output.append(current.data); current = current.next; } output.append("]"); return output.toString(); } public static void removeOddIntegers(LinkedList<Integer> list) { Node<Integer> dummy = new Node<Integer>(); dummy.next = list.head; Node<Integer> current = dummy; while (current != null) { if (current.next != null && current.next.data % 2 != 0) { current.next = current.next.next; } else { current = current.next; } } list.head = dummy.next; } public void removeEveryNthElement(int n) { Node<T> dummy = new Node<T>(); dummy.next = head; Node<T> current = dummy; int i = 1; while (current != null) { if (current.next != null && i % n == 0) { current.next = current.next.next; } else { current = current.next; } ++i; } head = dummy.next; } public int size() { Node<T> current = head; int size = 0; while (current != null) { ++size; current = current.next; } return size; } // Reverses a linked list. public void reverse() { Node<T> current = head; head = null; while (current != null) { Node<T> next = current.next; current.next = head; head = current; current = next; } } public void reverseHalves() { int size = size(); if (size < 2) return; reverse(); Node<T> current = head; int i = 0; int midpointIdx = size / 2; if (size % 2 == 0) --midpointIdx; Node<T> midpoint = null; while (true) { if (i == midpointIdx) midpoint = current; if (i == size - 1) { current.next = head; head = midpoint.next; midpoint.next = null; break; } ++i; current = current.next; } } public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<Integer>(); for (int i = 20; i >= 0; --i) list.add(i); System.out.println("list: " + list); removeOddIntegers(list); System.out.println("removeOddIntegers: " + list); int n = 2; list.removeEveryNthElement(n); System.out.println(String.format("removeEveryNthElement (n=%d): ", n) + list); list.reverseHalves(); System.out.println("reverseHalves: " + list); } }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);
}