Question

1. (20 points) ) Write a Python program which merges two sorted singly linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Example: Input: 1->2- >4, 1->3->4 Output: 1->1->2->3 ->4->4

Answer 1

answer :

class ListNode:
def _init_(self, x):
self.val = x
self.next = None


class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# Result ListNode
res = None

# Taking temporary lists
temp1 = l1
temp2 = l2

# Iterating over list 1
while True:
# If either of the list is empty
if temp1 == None or temp2 == None:
break
else:
# Comparing values
if temp2.val > temp1.val:
# Creating a temporary node
t1 = ListNode(temp1.val)
# Adding as first node
if res == None:
res = t1
else:
# Moving to last node
t = res
while t.next != None:
t = t.next
# Adding new node
t.next = t1
# Forwarding to next node
temp1 = temp1.next
# Comparing values
elif temp2.val < temp1.val:
# Creating a temporary node
t1 = ListNode(temp2.val)
# Adding as first node
if res == None:
res = t1
else:
# Moving to last node
t = res
while t.next != None:
t = t.next
# Adding new node
t.next = t1
# Forwarding to next node
temp2 = temp2.next
# Comparing values
else:
# Creating a temporary node
t1 = ListNode(temp1.val)
t2 = ListNode(temp2.val)
# Adding as first node
if res == None:
res = t1
res.next = t2
else:
# Moving to last node
t = res
while t.next != None:
t = t.next
# Adding new node
t.next = t1
t = t.next
t.next = t2
# Forwarding to next node
temp1 = temp1.next
temp2 = temp2.next
# Return new list
return res

def printList(l):
""" Function that prints the node """
temp = l;
# Iterating over list
while temp.next != None:
print(str(temp.val) + "->" , end="")
temp = temp.next
print(str(temp.val))

  
# Creating two Lists
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(4)
n2.next = n3
n1.next = n2
l1 = n1

n21 = ListNode(1)
n22 = ListNode(3)
n23 = ListNode(4)
n22.next = n23
n21.next = n22
l2 = n21

print("\nList 1: ", end="")
printList(l1)
print("\nList 2: ", end="")
printList(l2)

sObj = Solution()
rL = sObj.mergeTwoLists(l1, l2)
print("\n\nResult List: ", end="")
printList(rL)

___________________________________

Sample Run:(out put)

C:\Users\SaiBabu\AppData\Local\Programs\Python Python35>python d:\Python\ListNode.py List 1: 1->2->4 List 2: 1->3->4 Result List: 1->1->2-3-4->4 C:\Users\SaiBabu AppData\Local\Programs\Python Python35>