Given two sorted linked lists node0, and node, return a new sorted linked list containing the union of the two lists.
Constraints
0 ≤ n ≤ 100,000 where n is the number of nodes in node0
0 ≤ m ≤ 100,000 where m is the number of nodes in node1Example 1
Input
Visualize
ll0 = [1, 3, 4]
ll1 = [2, 3, 4]
Output
[1, 2, 3, 4]
Union Two Sorted Lists
Similar to Merge two Sorted Lists, the only difference is we need to check if two nodes are equal – in which case, only push once.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def unionTwoSortedLists(self, ll0, ll1): dummy = LLNode(-1) p = dummy while ll0 or ll1: if ll0 and ll1: if ll0.val < ll1.val: p.next = ll0 ll0 = ll0.next elif ll0.val > ll1.val: p.next = ll1 ll1 = ll1.next else: p.next = ll0 ll0 = ll0.next ll1 = ll1.next elif ll0: p.next = ll0 ll0 = ll0.next else: p.next = ll1 ll1 = ll1.next p = p.next return dummy.next |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def unionTwoSortedLists(self, ll0, ll1):
dummy = LLNode(-1)
p = dummy
while ll0 or ll1:
if ll0 and ll1:
if ll0.val < ll1.val:
p.next = ll0
ll0 = ll0.next
elif ll0.val > ll1.val:
p.next = ll1
ll1 = ll1.next
else:
p.next = ll0
ll0 = ll0.next
ll1 = ll1.next
elif ll0:
p.next = ll0
ll0 = ll0.next
else:
p.next = ll1
ll1 = ll1.next
p = p.next
return dummy.nextThe time complexity is O(M+N) where M and N is the length of two sorted link lists respectively. The space complexity is O(1) constant as we are not allocating additional space.
Recursive Union Algorithm for Two Sorted Link Lists
We can recursively pick the smaller node if possible and advance two linked lists pointers accordingly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def unionTwoSortedLists(self, ll0, ll1): if not ll0: return ll1 if not ll1: return ll0 if ll0.val < ll1.val: res = ll0 res.next = self.solve(ll0.next, ll1) elif ll1.val < ll0.val: res = ll1 res.next = self.solve(ll1.next, ll0) else: # ll0.val == ll1.val res = ll0 res.next = self.solve(ll0.next, ll1.next) return res |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def unionTwoSortedLists(self, ll0, ll1):
if not ll0:
return ll1
if not ll1:
return ll0
if ll0.val < ll1.val:
res = ll0
res.next = self.solve(ll0.next, ll1)
elif ll1.val < ll0.val:
res = ll1
res.next = self.solve(ll1.next, ll0)
else: # ll0.val == ll1.val
res = ll0
res.next = self.solve(ll0.next, ll1.next)
return resTime Complexity O(M+N) and space complexity is O(M+N) due to recursion.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Compute the Number of Trailing Zeros for Factorial N
Next Post: Compute the Inorder Successor of a Binary Tree
