LC 21 (with template)

Linked List

Publish Date: 2022-01-13

Solution to LeetCode 21 Merge two sorted lists.

LeetCode 21

Merge two sorted lists (Easy). [link]

1] Double Pointers.

Time complexity O(n + m), where n and m are the lengths of the two lists. Space complexity O(1).

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        tail = dummy = ListNode(0)
        while list1 and list2:
            if list1.val < list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
        tail.next = list1 if list1 else list2
        return dummy.next

2] Recursion

Time complexity O(n+m), space complexity O(n+m).

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1 or not list2:
            return list1 if list1 else list2
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Template for Recursive Merge Sort

List1 = [1,3,5], List2 = [2,4], merge in ascending order.

def merge(a,b):
    if not b: return a
    if not a: return b
    if a[0] < b[0]: 
            return a[0] + merge(a[1:], b)
    else:
          return a[0] + merge(a, b[1:])