[파이썬 알고리즘] 8장 - 두 정렬 리스트의 병합 (leetcode 21)

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

Merge Two Sorted Lists - LeetCode

<문제>

Merge two sorted linked lists and return it as a new sorted list.

The new list should be made by splicing together the nodes of the first two lists.

 

<예시>

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1,1,2,3,4,4]

 

---

지저분한 첫 답안 코드이다 ..

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 첫 답안
# 재귀보다는 살짝 빠르지만, 지저분하다 :(
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:

    # 이 부분도 불필요
    # merged를 return 하는 게 아니라, merged.next 리턴하면 해결될 문제 ..
    if l1 == None and l2 == None:
        return None

    merged = ListNode()  # (0, None)
    cur_node = merged
    l1_cur, l2_cur = l1, l2  # 불필요한 부분

    while (l1_cur != None) and (l2_cur != None):
        # l1_cur이나 l2_cur 중 하나가 None이 되면 while 탈출
        if l1_cur.val < l2_cur.val:
            cur_node.val, cur_node.next = l1_cur.val, ListNode()
            l1_cur = l1_cur.next
        else:
            cur_node.val, cur_node.next = l2_cur.val, ListNode()
            l2_cur = l2_cur.next
        cur_node = cur_node.next

    if l1_cur != None:
        # 이 부분 불필요 코드 축약 가능!
        while l1_cur.next != None :
            cur_node.val, cur_node.next = l1_cur.val, ListNode()
            cur_node = cur_node.next
            l1_cur = l1_cur.next
        cur_node.val = l1_cur.val
    if l2_cur != None:
        # 이 부분 불필요 코드 축약 가능!
        while l2_cur.next != None :
            cur_node.val, cur_node.next = l2_cur.val, ListNode()
            cur_node = cur_node.next
            l2_cur = l2_cur.next
        cur_node.val = l2_cur.val

    return merged

 

하지만 위의 너저분한 코드는 다음과 같이 수정이 가능하다!

def mergeTwoLists2(l1: ListNode, l2: ListNode) -> ListNode:

    merged = cur_node = ListNode() # (0, None)
    while l1 and l2:
        # print(f"l1 = {l1.val}, l2 = {l2.val}")
        if l1.val < l2.val:
            cur_node.next = l1
            l1 = l1.next
            cur_node = cur_node.next
        else:
            cur_node.next = l2
            l2 = l2.next
            cur_node = cur_node.next

    cur_node = l1 or l2
    # l1이 None이 아니면 l1이 리턴
    # l1이 None이면 l2가 리턴
    return merged.next

 

나의 지저분한 코드를 보면서 깨달음 점

1. l1_cur, l2_cur은 필요없다.
   1. 한 번 node를 보고난 다음 그 노드를 다시 볼 일이 없기 때문에 l1 = l1.next 이렇게 코드를 작성해도 괜찮다.
2. dummy node를 만들자
   1. dummy 노드를 만들지 않고 연결리스트의 첫 노드에도 데이터를 집어넣다보니 코드가 지저분해졌다.
   2. head 역할을 하는 dummy 노드를 만들고 head가 가리키는 첫 번째 node부터 데이터를 집어넣자!
   3. (+ 실제 이런 dummy 개념은 매우 자주 사용된다고 한다 .. 코드 작성의 편리함을 위해서!)
3. linked node의 특징을 기억하자.
   1. 처음 작성한 코드에서 A, B라는 두 개의 linked list가 있을 때, A의 내용은 merged list에 복사되었으나 B의 내용 중 뒷 부분의 내용이 복사되지 않았을 때 나는 하나하나 노드 만들고 이어주었다 : (
   2. 근데 그럴 필요가 없이 그냥 B 내용의 뒷 부분에 해당하는 첫 노드만 연결해주면 줄줄이 따라온다 ..
   3. 아주 불필요한 코드를 작성해버렸다 ..
4. return l1 or l2
   1. 처음에 이게 무엇인가 했는데 단순하다! l1이 false이면 l2를 return하고, l1이 true이면 l1을 return하라는 뜻이다.
      이것은 boolean algebra만 알고 있으면 쉽게 이해 가능하다!
      1. l1이 false이면 -> false or l2 = l2이므로 l2 리턴
      2. l1이 true이면 -> true or l2 = true 이므로 l1리턴
      3. 이런 식으로 동작하는 것 같다.

 

< 재귀 코드 >