# Splice-merge two sorted lists in Python

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
"""

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



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?

• 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
– Alex
Mar 27, 2019 at 10:04

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

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