Splice-merge two sorted lists in Python

Question

I tried to solve a merge two sorted list problem in leetcodes:

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

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        Plan:
        Compare l1 and l2 and merge the remainders
        """
        l3_head = ListNode(0)
        l3_cur = l3_head
        
        while l1 and l2: #assert both exist
            if l2.val < l1.val:
                l3_cur.next = l2 #build l3's node
                l2 = l2.next #this is i++ 
            else:
                l3_cur.next = l1
                l1 = l1.next     
            l3_cur = l3_cur.next #find the next to build
        if l1:
            l3_cur.next = l1 
        if l2:
            l3_cur.next = l2

        return l3_head.next

I assumed this is a decent solution but got:

Runtime: 56 ms, faster than 23.98% of Python3 online submissions for Merge Two Sorted Lists.

Memory Usage: 13.1 MB, less than 5.06% of Python3 online submissions for Merge Two Sorted Lists.

How could I improve my solution?

Answer 1

You shouldn't need to create a HeadNode, just use one of the ones given to you. Right now you relink every single item. But if one list has many sequential values, you could save time by just advancing to the tail. Also, right now you are checking 2 conditions in every loop even though only 1 changes.

You could try something like this: (after setting cur to the minimum node):

while True:
   while cur.next and cur.next.val <= l2.val:
       cur = cur.next
   cur.next = l2
   if not cur.next:  break

   while cur.next and l2.val <= l1.val:
       cur = cur.next
   cur.next = l1
   if not cur.next:  break