First, use the text book code on Linked List to create a header file and a .cpp file that describes the standard Linked List class and its functionalities. Next, incorporate the following two functions in your List class. Feel free to use the standard functions to help you write the following two functions.

1.) Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position. GetNth() uses the C numbering convention that the first node is index 0, the second is index 1, ... and so on. So for the list {42, 13, 666} GetNth() with index 1 should return 13. The index should be in the range [0..length-1]. If it is not, GetNth() should assert() fail (or you could implement some other error case strategy).

2.) Write a function Split() which given a list, splits it into two sublists one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list. So Split() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}. Getting this right for all the cases is harder than it looks. You should check your solution against a few cases (length = 2, length = 3, length=4) to make sure that the list gets split correctly near the short-list boundary conditions. If it works right for length=4, it probably works right for length=1000. You will probably need special case code to deal with the (length <2) cases.

Hint. Probably the simplest strategy is to compute the length of the list, then use a for loop to hop over the right number of nodes to find the last node of the front half, and then cut the list at that point. Write a driver program to test the different functions.

3 files header, .cpp, driver.