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?

• Alex: I suppose they are not using the 3rd list, in the end, you don't need that since instead of creating new nodes you are re-assigning values of old ones

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

• Graipher: If you replaced -> with ., && with and and ! with not , it would even be valid Python code :)
• AShelly: When you spend 90% of your day in C, it's hard not to let its syntax creep into your pseudocode :)