Merge Linked Lists

Max Reward: 100

Complete the merge() function that takes two linked lists and merges them to make a single list, taking nodes alternately from the supplied lists. If either list runs out, take all the remaining nodes from the other list.

Input Format

Your function gets two linked lists

Output Format

Return the new list

Sample Input

5
1 3 5 7 9
4
2 4 6 8

Sample Output

1 2 3 4 5 6 7 8 9

Memory Limit

512M