2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Alex Mar 27 at 10:04
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ If you replaced -> with ., && with and and ! with not , it would even be valid Python code :) \$\endgroup\$ – Graipher Mar 27 at 11:39
  • 1
    \$\begingroup\$ When you spend 90% of your day in C, it's hard not to let its syntax creep into your pseudocode :) \$\endgroup\$ – AShelly Mar 27 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.