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.

Advertisements

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

    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[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);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: