It is intuitive to create a dummy head then iteratively merge the 2 given sorted lists.
5/09/2020
[LeetCode] 21. Merge Two Sorted Lists
Problem : https://leetcode.com/problems/merge-two-sorted-lists/
Time Complexity = O( max ( len (l1), len(l2) )
Space Complexity = O ( 1 ). # merging is done in space.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
p = dummy
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
if l1:
p.next = l1
elif l2:
p.next = l2
return dummy.next
However, recursion approach is more elegant.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 and 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
elif l1:
return l1
elif l2:
return l2
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment