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:

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]

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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Some caveats:
        # One list may be longer than the other, in this case we just want to append that list onto our main list
        # we should a new empty list of ListNode, and return from the second node
        # for every node we determine which one is lower
        # if its lower, we put it first
        # we also need to be careful in case we have something likeL:
        # [1, 2] [5] -> 1, 2 should go first and then 5
        # so we need to not increment unless its lower
        SortedList = ListNode()
        # When we return, we want to return from the start of the list not the end. As we append to SortedList, we move up the list
        headOfSortedList = SortedList
        head1 = list1
        head2 = list2
        # while we have _some_ nodes
        while head1 or head2:
            # if either list has ended
            if not head1:
                SortedList.next = head2
                head2 = head2.next
            elif not head2:
                SortedList.next = head1
                head1 = head1.next
            else:
                # else both nodes have head
                if head1.val < head2.val:
                    # place head1 into sorted list
                    SortedList.next = head1
                    head1 = head1.next
                else:
                    # Else head2 is smaller
                    SortedList.next = head2
                    head2 = head2.next
            # go to next node
            SortedList = SortedList.next
        # The start of the list is an empty node we made so we can append to it, to get the "correct" list we need to .next() it
        return headOfSortedList.next