You might remember that we had a problem to merge two sorted linked lists at the beginning of the semester. Now we've learnt C++ ans thus the problem evolved a bit: templates, operator overloading are introduced, and we also micmic the behaviour of containers and iterators.
We declare the linked_list class with template, which has 2 member types (nested structs / classes), node & iterator. The former is for our private internal design purposes only, whereas the latter is public to others.
Most of the member functions have been done. You only need implement 3 ones: dereference iterators, forward iterators and merge two sorted linked lists. Make sure to read the instructions in the header carefully.
No parameter. The function would be called when *itr.
No parameter, too. The function would be called when ++itr.
The 2 parameters are the head of 2 sorted linked list.
It's guarantees that the sum of the total length of the linked list is less than 200000.
For the dereference operator of iterator, you should return the reference to which the iterator / node point to.
As for the pre-increment operator of iterator, you should forward that iterator and return the iterator itself.
Lastly, for the merge method of linked list, you should return the head of the merged list. Linear time complexity is expected .