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 

	## Read input as specified in the question.
	## Print output as specified in the question.
	class Node:
	def __init__(self,data):
	self.data=data
	self.next=None
	def LinkedLists(arr):
	head=None
	tail=None
	for i in arr:
	if i==-1:
	break
	data = Node(i)
	if head is None:
	head=data
	tail=data
	else:
	tail.next=data
	tail=data
	return head
	def MergeSortedLL(head1,head2):
	if head1 == None:
	return head2
	elif head2 == None:
	return head1
	mergedHead = None
	if head1.data <= head2.data:
	mergedHead = head1
	head1 = head1.next
	else:
	mergedHead = head2
	head2 = head2.next
	mergedTail = mergedHead
	while head1 != None and head2 != None:
	temp = None
	if head1.data <= head2.data:
	temp = head1
	head1 = head1.next
	else:
	temp = head2
	head2 = head2.next
	mergedTail.next = temp
	mergedTail = temp
	if head1 != None:
	mergedTail.next = head1
	elif head2 != None:
	mergedTail.next = head2
	return mergedHead
	def printLL(head):
	while head is not None:
	print(head.data,end=" ")
	head=head.next
	def printReverse(head) :
	prev = None
	current = head
	while (current is not None):
	next = current.next
	current.next = prev
	prev = current
	current = next
	head = prev
	printLL(head)
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	printLL(printReverse(MergeSortedLL(LinkedLists(arr1),LinkedLists(arr2))))

view raw Merge Two linked lists.py hosted with ❤ by GitHub