CS235-Project 4 Recursive Invert Solved

For this project you will modify a singly-linked list class (note this is different from the doubly-linked list of Project 3) by adding a method that will invert the order of the list. This method must be recursive and should not involve loops.

The idea: In a linked list it is possible to invert the order of its elements in O(n) time and in place (O(1) extra space) simply by changing the direction of the links:

head_ptr                                                          

head_ptr

To do so recursively, you can think of the solution to the problem as:


 

•       Split the list into first and rest







•       Reconnect rest to first in the appropriate direction


 




 head_ptr




Implementation:

In order to practice safe programming and not expose the structure of the list to clients of the class via pointer parameters, you will write a public non-recursive method invert that calls a private recursive method invertRest.


You must implement these methods in O(n) time and in place (you cannot use any additional list or other containers and cannot make copies of the nodes)
Should you write a solution that uses iteration instead of recursion and /or uses additional containers or copies to invert the list, I reserve the right to take away points even if Gradescope gives you full credit.

// A  wrapper to a recursive method that inverts the contents of the list

// @post the contents of the list are inverted such that

//      the item previously at position 0 is at position item_count_-1, //      the item previously at position 1 is at position item_count_-2 ...

//      the item previously at position ⌊item_count/2⌋ is at position                                                                         

         ⌈item_count_/2⌉ . . . 


//      the item previously at position item_count_-1 is at position 0 void invert();

//private function to invert, used for safe programming to avoid

//exposing pointers to list in public methods

// @post the contents of the list are inverted such that

//      the item previously at position 0 is at position item_count_-1, //      the item previously at position 1 is at position item_count_-2 ...

//      the item previously at position ⌊item_count/2⌋ is at position                                                                         

       ⌈item_count_/2⌉. . .


//     the item previously at position item_count_-1 is at position 0 void invertRest(Node<T* current_first_ptr);

Testing:  

In main() (not for submission) instantiate a LinkedList object and add data (nodes) to it. The list could be of any type and it should not affect execution. Once you have data in the list, call invert and make sure it works correctly (e.g. display the contents of the list to check that the order is the opposite in which you inserted the data items).

Also test that your methods run correctly on edge cases (e.g. empty list, single-node list).