CPS 100 Recitation #2 Warmup

1. Given the following picture

   

   and definition for a Node:

   struct Node { int value; Node * next; Node (int val, Node * link) : value(val), next(link) { } };

   write the code needed to build the structure in the above drawing

2. Write the function vec2list below that creates a linked list storing the same values that are stored in the given vector. The order of the linked list should be the same order as the vector (the first node of the linked list is a[0] in the function below). Node * vec2list(const tvector<int>& a) // pre: a contains a.size() entries, a.size() > 0 // post: return pointer to first node of linked list // containing same values as in a in same order { }
3. Write a function, cutInTwo, that cuts a linked-list into two equal new sub-lists (or lists whose size differs by one).

   That is, given a list with n elements where n is even, [a₁,a₂,a₃,...,a_n-1,a_n], cutInTwo truncates list to [a₁,...,a_n/2] and returns [a_n/2 + 1...,a_,n]. If n is odd, cutInTwo truncates list to [a₁,...,a_n/2 + 1] and returns [a_n/2 + 2...,a_,n].

   Fill in the function below.

     Node * cutInTwo(Node * list)
     // pre:  list is NULL/0 terminated, contains n nodes
     //       where n >= 0
     // post: list contains first n/2 (rounded up) nodes, and a pointer
     //       to the rest of the list
     //       so that effectively the list is cut in two.