[LeetCode] 21. Merge Two Sorted Lists 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Merge Two Sorted Lists

---

문제 요약

정렬된 두 개의 연결 리스트 list1, list2가 주어진다.
이 두 리스트를 하나의 정렬된 연결 리스트로 병합하고, 병합된 리스트의 head를 반환하라. 

 

✔ 문제 링크: https://leetcode.com/problems/merge-two-sorted-lists

---

📌 풀이 – 핵심 아이디어

1) 반복(iterative) 풀이

• Dummy Node를 만들어 head 처리의 복잡함을 제거한다.
• current 포인터를 두고 두 리스트를 비교하며 작은 값을 차례로 붙인다.
• 한 리스트가 먼저 끝나면 남은 리스트 전체를 그대로 붙인다. 

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode current = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        // 남은 리스트 연결
        if (list1 != null) current.next = list1;
        if (list2 != null) current.next = list2;

        return dummy.next;
    }
}

 

 

---

2) 재귀(recursive) 풀이

• 두 리스트 중 작은 값을 가진 노드를 선택하고
• 나머지 부분은 같은 함수에 다시 맡긴다. 

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

 

---

📊 시간 / 공간 복잡도

	시간 복잡도	공간 복잡도
반복	O(N + M)	O(1)
재귀	O(N + M)	O(N + M) 재귀 호출 스택

• N, M은 각 리스트의 길이

---

🧠 핵심 개념 & 정리

• Dummy Node 패턴
  → 연결 리스트 문제에서 head 처리와 예외 케이스를 단순화시켜준다. 

🔎 멘탈 모델

두 리스트를 앞에서부터 비교하여 점진적으로 병합한다.

 

📌 실수 방지

• dummy는 head 기준일 뿐,
  실제 결과는 dummy.next부터 시작함을 잊지 말자. 

💡 팁 / 트릭

• 한 리스트가 먼저 끝나면, 남은 노드 전체를 그냥 한 줄로 붙여주면 끝이다.

---

🧠 사고 과정

1. 두 리스트 모두 정렬되어 있기 때문에 앞에서부터 하나씩 비교한다.
2. Dummy Node를 먼저 둬서 head 처리의 예외를 제거한다.
3. 비교하면서 더 작은 노드를 current.next로 이어 붙인다.
4. current 포인터도 항상 한 칸씩 앞으로 이동한다.
5. 순회가 끝나면 남은 리스트를 그대로 이어준다.
6. 결과는 dummy.next에서 시작된다.

 

 

⭐ 이번 문제에서 얻은 깨달음

• 연결 리스트 문제는 포인터 이동 규칙이 핵심이다.
• Dummy Node는 단순 편의가 아니라 예외 케이스를 없애는 구조적 도구다.
• 반복과 재귀 각각의 사고 방식 모두 익혀두면 다양한 문제에 응용할 수 있다.
• 다음 질문에 YES라면 재귀가 가능하다.
  • “이 문제를 한 단계 줄여도 구조가 그대로인가?”