📌Problem

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.

leetcode 에서 풀기

---

📝Solution

# 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:
        
        
        head=ListNode(-1)
        cursor=head
        
        while l1!=None and l2!=None:
            if l1.val <= l2.val:
                cursor.next=l1 # Update next node
                l1=l1.next # Update l1
            else:
                cursor.next=l2 #Update next node
                l2=l2.next # Updata l2
            
            cursor=cursor.next #Move cursor
        
        
        # Last node  
        if l1!=None:
            cursor.next=l1
        
        else:
            cursor.next=l2
            
        return head.next

• Time complexity : $O(N)$