Problem Statement
Merge two sorted 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:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Solution:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#Recursive approach
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 or l2
if l1.val<l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
#Iterative approach
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 or l2
dummy = ListNode(0)
head = dummy
while l1!=None and l2!=None:
if l1.val<l2.val:
dummy.next = l1
l1 = l1.next
else:
dummy.next = l2
l2 = l2.next
dummy = dummy.next
if not l1 or not l2:
dummy.next = l1 or l2
return head.next
