[리트코드(LeetCode)] 21번 Merge Two Sorted Lists

문제

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

Merge Two Sorted Lists - LeetCode

정렬되어 있는 두 연결 리스트를 합치는 문제다.

예시

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

 

Example 2:

Input: list1 = [], list2 = []
Output: []

 

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

풀이

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        
        # 남은 노드 처리
        if list1:
            current.next = list1
        elif list2:
            current.next = list2

        return dummy.next

 

- 두 연결 리스트를 비교하면서 작은 값을 가진 노드를 새로운 리스트에 차례대로 추가하고 리스트의 포인터를 다음 노드로 이동시키는 과정을 반복한다.

- 두 리스트 중 하나가 끝날 때까지 반복하고, 남은 리스트를 처리하여 최종적으로 병합된 연결 리스트를 반환한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview