Problem Description

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

Merge the two lists into 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.jpg

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

Example 2:

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

My Idea

The idea here is to check which element has a lower value and set it as the next one in the list.

My solution

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Time Complexity: O(n)
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1:
        return list2
    if not list2:
        return list1

    res = ListNode()
    curr = res

    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr=curr.next

    if list1:
        curr.next = list1
    if list2:
        curr.next = list2

    return res.next