21. Merge Two Sorted Lists

원문: https://doljae.tistory.com/91

[Merge Two Sorted Lists - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com](https://leetcode.com/problems/merge-two-sorted-lists/)

1. 내 Trash Garbage 코드

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        zero_node = ListNode()
        cur = zero_node
        while l1 and l2:
            if l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next
        while l1:
            cur.next = l1
            l1 = l1.next
            cur = cur.next
        while l2:
            cur.next = l2
            l2 = l2.next
            cur = cur.next
        return zero_node.next

2. 개선된 코드

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        zero_node = ListNode()
        cur = zero_node
        while l1 and l2:
            if l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next
        cur.next = l1 or l2
        return zero_node.next

특정 Linked-list를 먼저 다 사용했다면, 나머지를 그냥 붙여주기만 하면 되기 때문에 굳이 반복문을 돌릴 필요가 없다.

3. Recursive Solution

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:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

재귀 코드는 정말 보면 볼수록 디자인을 하는 게 너무 신기한 것 같다.

특히 Python은 다른 언어보다 문법이 간결한데 재귀까지 예쁘게 사용하면 정말...