Merge Two linked lists

Level MEDIUM

Given two linked lists sorted in increasing order. Merge them such a way that the result list is in decreasing order (reverse order).

Try solving without reverse, with O(1) auxiliary space (in-place) and only one traversal of both lists. You just need to return the head of the new linked list, don't print the elements.

Input format :

Line 1 : Linked list 1 elements of length n (separated by space

and terminated by -1)
Line 2 : Linked list 2 elements of length m (separated by space 

and terminated by -1)

Output format :

Merged list elements (separated by space)

Constraints :

1 <= n, m <= 10^4

Sample Input :

 2 5 8 12 -1
 3 6 9 -1

Note: -1 at the end of input is just a terminator representing the end of the linked list. This -1 is not part of the linked list. Size of 1st linked list is 4 and that of 2nd linked list is 3.

Sample Output :

 12 9 8 6 5 3 2