21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: l1 = [], l2 = []
Output: []

Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

Solution in python:

# 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: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        result = l1 if l1.val<l2.val else l2
        pre = None
        while l1 and l2:
            while l1 and l2 and l1.val < l2.val:
                pre = l1
                l1 = l1.next
            if pre != None:
                pre.next = l2
            if l1 == None or l2 == None:
                break
            while l1 and l2 and l2.val <= l1.val:
                pre = l2
                l2 = l2.next
            if pre != None:
                pre.next = l1

        return result