## Three More List Manipulation Exercises

### October 14, 2016

We have three more list-manipulation exercises today, for those students midway through their beginning programming course who need practice with linked lists:

1. Define a function that takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list.
2. Rearrange the integers in a list so that all the odd numbers appear before all the even numbers, with both odd and even numbers in the same relative order in the output as they were in the input.
3. Write a function that returns the nth item from the end of a list.

Your task is to write the three specified programs. 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 More List Manipulation Exercises”

1. Daniel said

Here’s a solution in Java.

```public class LinkedList<T> {
public static class Node<U> {
U data;
Node<U> next;
}

Node<T> node = new Node<>();
node.data = value;
}

@Override
public String toString() {
StringBuffer output = new StringBuffer("[");
for (Node<T> n = head; n != null; n = n.next) {
if (n != head) output.append(", ");
output.append(n.data);
}
output.append("]");
return output.toString();
}

// Reverses a linked list in-place.
public void reverse() {
while (current != null) {
Node<T> next = current.next;
current = next;
}
}

while (current != null && currentCount != null) {
for (int i = 0; i < currentCount.data; ++i) {
}
current = current.next;
currentCount = currentCount.next;
}
return output;
}

for (Node<Integer> n = list.head; n != null; n = n.next) {
if (n.data % 2 != 0) output.add(n.data);
}
for (Node<Integer> n = list.head; n != null; n = n.next) {
if (n.data % 2 == 0) output.add(n.data);
}
output.reverse();
return output;
}

// n = 0 returns the last element.
// Will throw an NPE if n is negative or too big (which is always the case for
// an empty list).
public T nthFromEnd(int n) {
Node<T> nthFromEnd = null;
int count = 0;
for (Node<T> node = head; node != null; node = node.next) {
if (nthFromEnd != null) nthFromEnd = nthFromEnd.next;
if (count++ == n) nthFromEnd = head;
}
return nthFromEnd.data;
}

public static void main(String[] args) {
int size = 10;
for (int i = size-1; i >= 0; --i) list.add(i);
System.out.println("list:\n  " + list);
for (int i = 0; i < size; ++i) counts.add(i % 2 == 0 ? 1 : 2);
System.out.println("counts:\n  " + counts);
System.out.println("repeats(list, counts):\n  " + repeats(list, counts));
System.out.println("rearrange(list):\n  " + rearrange(list));
int n = 3;
System.out.println(
String.format("list.nthFromEnd(%d):\n  ", n) + list.nthFromEnd(n));
}

}
```

Output:

```list:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
counts:
[2, 1, 2, 1, 2, 1, 2, 1, 2, 1]
repeats(list, counts):
[9, 8, 8, 7, 6, 6, 5, 4, 4, 3, 2, 2, 1, 0, 0]
rearrange(list):
[1, 3, 5, 7, 9, 0, 2, 4, 6, 8]
list.nthFromEnd(3):
6
```
2. V said
```
a.zip(b).flat_map { |x, n| n.times.map { x } }.reverse
end

list.partition(&:odd?).flatten
end

list.reverse[n]
end

```
3. My solution in clojure:

```(defn t1 [l1 l2]
(mapcat #(repeat %2 %1) (reverse l1) l2))

(defn t2 [l]
(flatten (conj (filter even? l) (filter odd? l))))

(defn t3 [l n]
(nth (reverse l) n ))
```

Output:

(t1 ‘(2 3 4 1) ‘(4 5 6 1)) => (1 1 1 1 4 4 4 4 4 3 3 3 3 3 3 2)

(t2 ‘(1 2 3 4 5 6 7 8)) => (1 3 5 7 2 4 6 8)

(t3 ‘(1 2 3 4 5 5 6 7) 3) => 5

4. Daniel said

@miguelpinia, it looks like we had different interpretations of task 1. I associated “reverse order” with the returned list. It looks like you associated “reverse order” with the input list.

Here’s the Clojure version of my interpretation, based on your code.

```(defn t1 [l1 l2]
(reverse (mapcat #(repeat %2 %1) l1 l2)))
```

@V, are your functions intended to operate on Ruby Arrays? My interpretation of the problem was that ‘list’ refers to ‘linked list’ (based on the comment, “… practice with linked lists”), but after reading again I see that the tasks all say ‘list’, not ‘linked list’.

5. V said

@miguelpinia There are no build-in linked lists in Ruby, so my implementation is intended for Arrays. I thought for this simple exercise LinkedList, List or Array could be used interchangeably.

6. matthew said

@Daniel: It does mention “practice with linked lists” in the first line. Makes a nice exercise in pointer manipulation. Here’s C++ solutions to a couple of the previous set of exercises and the odd/even rearrangement problem:

```#include <stdio.h>
#include <stdlib.h>

struct Node {
Node(int n_, Node* next_) : n(n_), next(next_) {}
int n; Node *next;
};

void removeodd(Node **p) {
while(*p) {
if ((*p)->n%2) {
*p = (*p)->next;
} else {
p = &(*p)->next;
}
}
}

void swaphalves(Node **p) {
if(!*p) return;
int i, j; Node *q = *p, *r = *p;
for (i = 1; q->next; i++, q = q->next);
for (j = 1; j < i/2; j++, r = r->next);
q->next = *p; *p = r->next; r->next = 0;
}

void split(Node **root) {
Node **oend = root, *estart = 0, **eend = &estart;
for (Node *p = *root; p; p = p->next) {
if (p->n%2) {
*oend = p; oend = &p->next;
} else {
*eend = p; eend = &p->next;
}
}
*oend = estart; *eend = 0;
}

void show(Node *p) {
printf("[ ");
for ( ; p; p = p->next) {
printf("%d ", p->n);
}
printf("]\n");
}

int main(int argc, char *argv[]) {
Node *s = 0;
for (int i = 1; i < argc; i++) {
s = new Node(atoi(argv[argc-i]),s);
}
show(s);
split(&s); show(s);
swaphalves(&s); show(s);
removeodd(&s); show(s);
}
```