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

1. Write a function that takes a linked list of integers and returns a new linked list with all the odd integers removed.
2. Write a function that removes every nth item from a linked list.
3. 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.

Pages: 1 2

### 7 Responses to “Three List Manipulation Exercises”

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

2. V said

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
end

```
3. Ilija said

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

“`

4. Ilija said

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

5. Daniel said

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> node = new Node<T>();
node.data = element;
}

@Override
public String toString() {
StringBuffer output = new StringBuffer("[");
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>();
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;
}
}
}

public void removeEveryNthElement(int n) {
Node<T> dummy = new Node<T>();
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;
}
}

public int size() {
int size = 0;
while (current != null) {
++size;
current = current.next;
}
return size;
}

public void reverse() {
while (current != null) {
Node<T> next = current.next;
current = next;
}
}

public void reverseHalves() {
int size = size();
if (size < 2) return;
reverse();
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) {
midpoint.next = null;
break;
}
++i;
current = current.next;
}
}

public static void main(String[] args) {
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:

```list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
removeOddIntegers: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
removeEveryNthElement (n=2): [0, 4, 8, 12, 16, 20]
reverseHalves: [8, 4, 0, 20, 16, 12]
```
6. Aquiles Peña said

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,true);
\$m2=array_reverse(\$ays,true);
if(\$odd) {
\$m3=array_reverse(\$ays,true);
\$m=\$m1+\$m3+\$m2;
}
else {
\$m=\$m1+\$m2;
}
return print_r(\$m);
}