[오늘의 문제] 정렬된 두 리스트 병합

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

21. 정렬된 두 리스트 병합
    쉬운
    주제
    프리미엄 잠금 아이콘
    회사들
    list1정렬된 두 연결 리스트의 첫 번째 요소 와 두 번째 요소가 주어집니다 list2.

두 개의 리스트를 하나의 정렬된 리스트로 병합하세요. 이 리스트는 첫 번째와 두 번째 리스트의 노드들을 연결하여 만들어야 합니다.

병합된 연결 리스트의 첫 번째 요소를 반환합니다 .

예시 1:

입력: list1 = [1,2,4], list2 = [1,3,4]
출력: [1,1,2,3,4,4]
예시 2:

입력: list1 = [], list2 = []
출력: []
예시 3:

입력: list1 = [], list2 = [0]
출력: [0]

제약 조건:

두 목록 모두의 노드 수는 범위 내에 있습니다 [0, 50].
-100 <= Node.val <= 100
list1와 는 모두 오름차순list2 으로 정렬되어 있습니다

내가 한 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:

    list1 = [1,2,4]
    list2 = [1,3,4]
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        a = list1
        b = list2

        a.extend(b)
        a.sort()
        return a 

    
    mergeTwoLists(list1, list2)
        

트러블 슈팅

TypeError: Solution.mergeTwoLists()에 필수 위치 인수 'list2'가 누락되었습니다. mergeTwoLists(list1, list2) Solution(Solution.py)의 22번째 줄 클래스 Solution: (Solution.py)의 8번째 줄

이런 에러가 뜬다.

이 함수는 첫 번째 인자로 자기 자신인 self를 받게 된다. 그런데 마지막 줄에서 mergeTwoLists(list1, list2)라고 호출하면, 파이썬은 self 자리에 list1을 넣고, list1 자리에 list2를 넣는다. 결과적으로 세 번째 인자인 list2에 들어갈 값이 없어서 에러가 발생

LeetCode 같은 플랫폼에서는 클래스 내부에서 직접 호출하지 않는다. 테스트를 해보고 싶다면 클래스 외부에서 인스턴스를 만든 뒤 호출해야 한다.

. 문제에서 주어지는 list1과 list2는 파이썬의 기본 리스트([1, 2, 4])가 아니라 연결 리스트(Linked List) 객체이며, sort, extend는 일반 파이썬 list에서만 사용가능한 메서드이다.

모범답안

class Solution:
  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
      # 결과를 담을 가짜(Dummy) 노드를 만듭니다.
      dummy = ListNode()
      tail = dummy
      
      # 두 리스트를 순회하며 작은 값을 선택해 연결합니다.
      while list1 and list2:
          if list1.val < list2.val: # 1번 기차의 값과 2번 기차의 값을 비교!
              tail.next = list1 # 더 작은 값을 가진 노드를 결과 기차 뒤에 연결!
              list1 = list1.next # 1번 기차는 이제 한 칸 앞으로 이동!
          else:
              tail.next = list2
              list2 = list2.next
          tail = tail.next
      
      # 남은 노드가 있다면 통째로 붙여줍니다.
      tail.next = list1 if list1 else list2
      
      return dummy.next

# --- 테스트를 위해 실행하는 법 (클래스 밖에서) ---
# sol = Solution()
# result = sol.mergeTwoLists(node1, node2)