21. Merge Two Sorted Lists

Updated: 2024-02-24
2 min read
[Linked List Recursion]

LeetCode problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

21. Merge Two Sorted Lists

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = [0]
Output: [0]

First accepted

Idea:

Get smallest head. Loop and update its next.

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        res = ListNode()
        current = res
        while l1 and l2:
            if l1.val <= l2.val:
                node = ListNode(l1.val)
                l1 = l1.next
            else:
                node = ListNode(l2.val)
                l2 = l2.next
            current.next = node
            current = current.next

        if l1:
            current.next = l1
        if l2:
            current.next = l2

        return res.next

Better solution

Recursion

def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
 if l1 and l2:
  if l1.val > l2.val:
   l1, l2 = l2, l1 #swap smaller and larger: make l1 the one with the smaller first value
  l1.next = self.mergeTwoLists(l1.next, l2) # move forward in the list which starts with the smaller value
 return l1 or l2 # return whichever of the two lists remains at the end

Loop

def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        res = ListNode()
        current = res
        while l1 and l2:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
                
class Solution:
    def mergeTwoLists(self, a, b):
        if a and b:
            if a.val > b.val:
                a, b = b, a
            a.next = self.mergeTwoLists(a.next, b)
        return a or b

First make sure that a is the “better” one (meaning b is None or has larger/equal value). Then merge the remainders behind a.

def mergeTwoLists(self, a, b):
    if not a or b and a.val > b.val:
        a, b = b, a
    if a:
        a.next = self.mergeTwoLists(a.next, b)
    return a