Leetcode 21. Merge Two Sorted Lists

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:

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

Example 2:Input: list1 = [], list2 = [] Output: []

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

Constraints:

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

The concept of this problem is only about how much you know about operating linked list.

So, we only need to have 2 variables to remember where is head and tail, then go through 2 lists to re-organize.

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = None
        tail = None

        while list1 is not None and list2 is not None:
            if head is None:
                if list1.val < list2.val:
                    head = list1
                    list1 = list1.next
                else:
                    head = list2
                    list2 = list2.next
                
                tail = head
            else:
                if list1.val < list2.val:
                    tail.next = list1
                    list1 = list1.next
                else:
                    tail.next = list2
                    list2 = list2.next

                tail = tail.next
        
        if tail is None:
            if list1 is None:
                head = list2
            else:
                head = list1
        else:
            if list1 is None:
                tail.next = list2
            else:
                tail.next = list1
        
        return head