LeetCode 21. Merge Two Sorted Lists

파이썬 알고리즘 인터뷰 문제 14번(리트코드 21번) Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/

나의 풀이

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        new = ListNode(0)
        curr = new
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        if l1:
            curr.next = l1
        if l2:
            curr.next = l2
        return new.next

간단한 풀이이다.
dummy를 만들고 그 뒤에 l1, l2를 순회하며 작은 노드를 이어준다.
그러다가 l1, l2 중 하나가 바닥이 나면 남은 것을 이어준다.

다른 풀이(재귀, recursive)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


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

와... 처음에 보고 정말 머리에 쥐가 났다.
크게 두 부분이 어려웠다.
한참을 봐도 이해가 잘 안되었었는데, 두 번째 보니까 스스로 작성할 수 있었다.
복습 필수!

1. 스왑 부분
   l1, l2를 바꾸는 부분이 있다.
   이 함수는 작은 값인 l1을 return한다.
   그렇다면 둘을 바꿔줘야 하는 경우는
   1) l2가 더 작은 경우이다.
   그런데 대소 비교를 하려면 둘 다 값이 있어야 하므로 이 경우는
   l1 and l2 and l1.val > l2.val이라 할 수 있다.
   2) l1은 None이고 l2는 None이 아닌 경우에도 순서를 바꿔야한다.
   not l1 and l2라 할 수 있다.
   이를 종합하면 (not l1 and l2) or (l1 and l2 and l1.val > l2.val이다.
   그런데 이를 간단히하면 (not l1) or (l2 and l1.val > l2.val라 할 수 있다.
   왜냐하면 or 뒤쪽을 참 거짓을 따진다는 것은 앞쪽의 not l1은 거짓이다.
   즉, 뒤쪽을 따질 때는 당연히l1이라는 것이다.

2. 재귀 부분
   작은 순서대로 이어주어야하므로 결국 핵심은 값이 작은 노드를 가져오는 것이다.
   1번 스왑부분을 이용해서 l1, l2중 작은 l1을 가져와서 return하게 되어있다.
   그렇다면 가장 작은 l1을 가져왔다면 그 다음 해야하는 일은 무엇인가?
   나머지 중에서 또 가장 작은 것을 가져와서 l1.next에 이어주어야한다.
   따라서 l1,next, l2중 작은 것을 가져와서 이어준다.
   즉, l1.next = self.mergeTwoLists(l1.next, l2)하면 된다.