파이썬 알고리즘 인터뷰 14번 두 정렬 리스트 병합(리트코드 21번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Solution

# 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]:
        if list1 is None and list2 is None:
            return None

        start = ListNode()
        curr = start

        while list1 is not None or list2 is not None:
            if list1 is None:
                new_node = ListNode(list2.val)
                list2 = list2.next

            elif list2 is None:
                new_node = ListNode(list1.val)
                list1 = list1.next

            elif list1.val > list2.val:
                new_node = ListNode(list2.val)
                list2 = list2.next
            else:
                new_node = ListNode(list1.val)
                list1 = list1.next
            curr.next = new_node
            curr = curr.next

        return start.next

list1, list2의 값을 비교하면서 더 작은 값을 이용하여 새로운 연결 리스트를 만들었다.

Reference

파이썬 알고리즘 인터뷰