Merge two sorted linked lists

This is the Leetcode question #21

Merge Two Sorted Lists - LeetCode

This is similar to merge two sorted arrays. One difference is that we should have two pointers.

One of them helps us return the new linked list when we finish merging two linked lists since once we go to the end of a linked list, we cannot go backward to the front. The other is similar compare to the cursor in the merge two sorted arrays problem.

One special case, if one of l1 or l2 is already null, then there is no operation to merge. We can simply add it to the end of new linked list.

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    new_list = ListNode(0)
    new_copy = new_list
    while l1 is not None and l2 is not None:
        if l1.val > l2.val:
            new_copy.next = ListNode(l2.val)
            new_copy = new_copy.next
            l2 = l2.next
        else:
            new_copy.next = ListNode(l1.val)
            new_copy = new_copy.next
            l1 = l1.next
    if l1:
        new_copy.next = l1
    if l2:
        new_copy.next = l2
    return new_list.next