Introduction

You are to write solutions to each of the problems given below. You should not spend time debugging them, running them, or testing them. These exercises are designed to have you think about what you're doing without using the computer. You should feel free to use the compiler to assist with syntactic errors, however, if you think this will be useful. You should type solutions to these problems using emacs (or some editor on your own machine) and submit the solution using the submit program: 
    submit100 link solution
Be sure to include your name, the time you spent, and a list of collaborators in the file solution (there's no need for a separate README file). In all these problems assume that type Node exists as shown below. 
    struct Node 
    {
        string info;
        Node * next;
        Node(const string & s, Node * follow = 0){    // constructor
            info = s;
            next = follow;
        }
    };

Problem 1: Count

Complete the function TotalChars TotalChars returns the total number of (non-null) characters in all the strings in its parameter list . You may use either {\tt strlen()} or the member function length() . as in {\tt str.length()} that is supplied with the class string . You should write this function both recursively and iteratively (non-recursively). 
    int TotalChars(Node * list)
    // precondition: list has no header node
    // postcondition: returns total of chars in list

Problem 2 : Double

Write the function Double whose header is given below. Double adds new nodes to the list so that all nodes are, in effect, doubled. Thus the list ("apple","cat","xray") becomes ("apple","apple","cat","cat","xray","xray") when it's doubled. 
    void Double(Node * list)
    // precondition: list = a1, a2, ... an
    // postcondition: list  = a1, a1, a2, a2, ..., an, an

Problem 3: Reverse

Complete the function Reverse whose header is given below. Reverse reverses the nodes of its parameter list . You should do this by manipulating pointers, not by swapping info fields. In writing Reverse you should maintain as an invariant the picture shown in the figure below. This invariant would be initialized by the statement: rev = NULL . since initially no nodes have been reversed and all nodes need to be reversed. 
    void Reverse(Node * & list)
    //precondition: list represents the list \(a\sb{1},a\sb{2},\ldots a\sb{n}\)
    //postcondition: list represents \(a\sb{n},\ldots a\sb{2},a\sb{1}\)

Pictorial invariant for linked-list reversal. 

                            rev    list
                             /       \
                            /         \
          +---+   +---+   +---+      +---+   +---+   +---+
     ||<--|   |<--|   |<--|   |	     |   |-->|   |-->|   |-->||
          +---+	  +---+	  +---+	     +---+   +---+   +---+
 
            nodes reversed so far       nodes needing to be reversed

Problem 4: Remove

Write a function Remove that will remove all nodes containing a specified string from a list. Assume that lists do NOT have header nodes and that the call Remove(list,"big") removes all nodes containing the word "big" from list . You should write this function both iteratively and recursively.

Problem 5: Split++

Write a function ListSplit that will split a circular list containing an even number of nodes, say 2k, into two circular lists each of which contains k nodes. The function should have three parameters and should work so that the function call 
          ListSplit(list,sub1,sub2);
will create new lists pointed to by parameters sub1, and sub2 from the list initially referenced by parameter list. After ListSplit is called, the first parameter should be NULL, i.e., new nodes are NOT created, but are redistributed evenly between the second and third parameters. It doesn't matter how you divide the nodes between the two lists. The prototype for the function is: 
        void ListSplit(Node * & list, Node * & first, Node * & second);
(extra credit if you develop a useful invariant for your code)