Algorithms to Union Two Sorted Linked Lists

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 node1

Example 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.

# 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

The 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.

# 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

Time Complexity O(M+N) and space complexity is O(M+N) due to recursion.

–EOF (The Ultimate Computing & Technology Blog) —