Write a function named middle that returns the middle value in a linked list of integers.
The middle value is one halfway down the list.
For example, if the list is [11, -2, 45, 39, 84], you should return 45.
If the list is of even length, return the rightmost of the two middle elements.
For example, if the list is [11, -2, 88, 45, 39, 0], you should return 45.
If the list is empty, you should throw a string exception.
(For added challenge, can you solve this problem while traversing the list only once?)
Assume that you are using the ListNode structure as defined below:
struct ListNode {
int data; // value stored in each node
ListNode* next; // pointer to next node in list (nullptr if none)
}
