← 전체 회차
A-036● Day 362026.06.11easyleetcode #21neetcode150

정렬된 두 연결 리스트 병합

#linked-list#recursion
↗ leetcode #21 · merge-two-sorted-lists
01

문제

· problem
P.036

정렬된 두 연결 리스트 병합

↗ leetcode #21

두 개의 정렬된 연결 리스트 list1과 list2의 헤드가 주어진다. 두 리스트를 하나의 정렬된 리스트로 병합하라. 리스트는 두 리스트의 노드들을 함께 연결하여 만들어야 한다. 병합된 연결 리스트의 헤드를 반환하라.

제약
  • · Number of nodes in both lists: [0, 50]
  • · -100 ≤ Node.val ≤ 100
  • · Both lists are sorted in non-decreasing order
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,4]
[1,3,4]
[1,1,2,3,4,4]
example 2input → output
[]
[]
[]
example 3input → output
[]
[0]
[0]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    새 노드를 생성해야 하나요, 아니면 기존 노드들을 재배열하나요?
  • ☐
    두 리스트가 모두 비어있으면 뭘 반환해야 하나요?
  • ☐
    리스트에 중복된 값이 있을 수 있나요?
  • ☐
    입력 리스트들이 반드시 정렬되어 있다고 보장할 수 있나요?
  • ☐
    원본 리스트의 구조를 수정해도 괜찮나요?
  • ☐
    병합된 리스트를 한 번 더 정렬해야 하나요?
  • ☐
    병합 리스트를 위해 별도로 메모리를 할당해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 더미 노드 초기화
○
dummy = node = ListNode()
○
dummy = ListNode(0)
○
node = None
step 2· 두 리스트 모두에 노드가 있는 동안 반복
○
while list1 and list2:
○
while list1 or list2:
○
while True:
step 3· 더 작은 값을 비교하고 연결│ 중첩
○
if list1.val < list2.val:
○
if list1.val <= list2.val:
○
if list1.val > list2.val:
step 4· 병합된 리스트 포인터 이동│ 중첩
○
node = node.next
○
dummy = dummy.next
○
node.next = node.next.next
step 5· 남은 노드들 연결
○
node.next = list1 or list2
○
return list1 or list2
○
node.next = list1 + list2
step 6· 병합된 리스트의 헤드 반환
○
return dummy.next
○
return dummy
○
return node
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
7
# Iterative
8
class Solution:
9
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
10
        dummy = node = ListNode()
11
12
        while list1 and list2:
13
            if list1.val < list2.val:
14
                node.next = list1
15
                list1 = list1.next
16
            else:
17
                node.next = list2
18
                list2 = list2.next
19
            node = node.next
20
21
        node.next = list1 or list2
22
23
        return dummy.next
24
    
25
# Recursive
26
class Solution:
27
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
28
        if not list1:
29
            return list2
30
        if not list2:
31
            return list1
32
        lil, big = (list1, list2) if list1.val < list2.val else (list2, list1)
33
        lil.next = self.mergeTwoLists(lil.next, big)
34
        return lil
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,4]
[1,3,4]
→
[1,1,2,3,4,4]
case 2
[]
[]
→
[]
case 3
[]
[0]
→
[0]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.