[LeetCode] #21. Merge Two Sorted Lists

#21. 두 정렬 리스트의 병합

문제

문제 링크
이미 정렬된 두 개의 연결리스트가 주어졌을 때 순서대로 두 연결리스트를 병합해라.

풀이

주어진 리스트가 이미 정렬되어 있기 때문에 L1과 L2의 요소를 하나씩 접근해 비교하면서 작은 요소를 output에 넣는다. L1, L2 중 한 리스트에만 요소가 존재한다면 남아있는 요소를 모두 output에 넣는다. 합병 정렬에서 맨 마지막 단계와 동일한 방법이다. 단계별 과정을 아래에 그려보았다.

1) 합병된 결과를 가리키는 ListNode형태의 dummy를 하나 만든다. dummy는 결과 리스트의 시작노드인 head를 가리킨다.
2) 파란색 포인터처럼 L1, L2 요소를 하나씩 접근해 값이 작은 요소를 dummy에 add한다.
3) L1, L2 중 하나만 존재하면 나머지 요소를 모두 dummy에 넣는다.

👉 결과적으로 dummy는 결과 리스트의 시작노드인 head를 가리키고, tail은 결과 리스트의 마지막노드를 가리킨다.

코드

github

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:
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        elif l2:
            tail.next = l2
        return dummy.next

참고 : NeetCode