[PYTHON] Let Code Day24 Starting from Zero "21. Merge Two Sorted Lists"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 23 "226. Invert Binary Tree" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

21. Merge Two Sorted Lists

Given two sorted linked lists, merge them and return a new list.

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

solution

I wanted to solve it using the iterative method, so this time I will post two methods, recursion and iterative method.

First is recursion.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 or not l2:
            return l1 or l2
        if l1.val >= l2.val:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
        else:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
# Runtime: 32 ms, faster than 89.62% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.8 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

I prefer recursion because it's simple and cohesive and very readable. It's also easier to write.

Next is an example of writing in the iterative method.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        temp = ans = ListNode(0)
        while l1 or l2:
            if l1 and l2:
                if l1.val < l2.val:
                    ans.next = l1
                    l1 = l1.next
                else:
                    ans.next = l2
                    l2 = l2.next
            elif l1:
                ans.next = l1
                l1 = l1.next
            elif l2:
                ans.next = l2
                l2 = l2.next
            ans = ans.next
        return temp.next

# Runtime: 28 ms, faster than 97.54% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.9 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

The basic idea is to process by conditional branching while a specific element exists. In this example, processing is continued while l1 and l2 of ListNode exist, and if both exist, the values are compared and the smaller one is assigned to ʻans`, which is finally returned. This is how it is written because it is sufficient to move the element of ListNode that has no elements back by one.

This is easy for anyone to understand, but at the same time it feels a bit redundant. So I rewrote it.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        temp = ans = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                ans.next = l1
                l1 = l1.next
            else:
                ans.next = l2
                l2 = l2.next
            ans = ans.next
        ans.next = l1 or l2 
        return temp.next
# Runtime: 36 ms, faster than 70.49% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 14 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.

What has changed is that the condition of the while statement has changed from ʻor to ʻand, and with that change.

ans.next = l1 or l2

Is added. By doing this, the redundant part was greatly reduced. It will compare while both l1 and l2 are present, and if only one is present, it will substitute the rest in that order.

If there is a good answer, I will add it.