Merge Two Sorted Lists

문제

두 개의 정렬된 연결 리스트 'list1'와 'list2'의 헤드가 주어집니다. 이 두 리스트를 하나의 정렬된 리스트로 병합하세요. 이 리스트는 처음 두 리스트의 노드들을 연결함으로써 만들어져야 합니다. 병합된 연결 리스트의 헤드를 반환하세요.

접근 방향

두 연결리스트를 각각 순회하면서 노드의 값을 하나의 배열에 담은 후 담은 배열을 오름차순으로 정렬 후에 이 배열을 순회하면서 차례로 노드를 생성합니다.

나의 풀이

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

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """

        # 두 연결리스트의 노드 값을 담을 배열 생성
        bucket = []

        # 첫 번째 연결리스트 순회
        while list1:
            bucket.append(list1.val)
            list1 = list1.next

        # 두 번째 연결리스트 순회
        while list2:
            bucket.append(list2.val)
            list2 = list2.next

        # 신규 노드를 생성하기 더미 노드 생성
        dummy = ListNode(0)
        # 현재 노드를 cur 변수에 담기 (tail)
        cur = dummy

        # 오름차순으로 정렬된 배열을 순회
        for i in sorted(bucket):
            # cur.next에 노드 생성 후 다음 노드 이동
            cur.next = ListNode(i)
            cur = cur.next

        # 더미 노드의 다음 노드부터 값이 들어가므로
        # dummy.next 반환 (head)
        return dummy.next