[링크드 리스트 (Linked List)] LC #21 Merge Two Sorted Lists

문제 설명

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

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

1. 문제의 핵심: 더미 노드(Dummy Node)와 포인터

이 문제는 링크드 리스트를 다루는 가장 기본적인 테크닉 중 하나를 사용합니다. 새로운 리스트를 만들어 나갈 때, 시작 노드(head)를 어떻게 처리할지 고민하는 것은 매우 번거롭습니다. 첫 노드를 정하고 나면 그 다음부터는 `next`에 붙여나가면 되지만, 첫 노드를 정하는 과정 자체가 예외 처리를 요구하기 때문입니다.

핵심 아이디어: 실제 데이터를 담지 않는 '가짜' 머리 노드, 즉 더미 노드(dummy node)를 만들어두면, 모든 노드를 동일한 로직으로 처리할 수 있다.

더미 노드를 만들고, 실제 병합된 노드들은 이 더미 노드의 `next`부터 연결해 나갑니다. 마지막에 `dummy.next`를 반환하면 깔끔하게 병합된 리스트의 진짜 시작점을 얻을 수 있습니다.

2. 해결 전략: 반복문을 이용한 병합

1. dummy 노드와, 병합된 리스트의 마지막을 가리킬 current 포인터를 생성합니다. (초기값: current = dummy)
2. list1과 list2가 모두 `null`이 아닐 동안 반복합니다.
3. list1.val과 list2.val을 비교하여 더 작은 쪽의 노드를 current.next에 연결합니다.
4. current 포인터를 지금 연결한 노드로 한 칸 이동시킵니다. (current = current.next)
5. 값이 선택된 리스트의 포인터를 다음 노드로 이동시킵니다.
6. 반복문이 끝나면, 둘 중 하나에 남아있는 노드들을 current.next에 통째로 붙여줍니다.
7. 최종적으로 dummy.next를 반환합니다.

3. Java 코드 구현

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. 더미 노드와 현재 포인터 생성
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        // 2. 두 리스트 중 하나가 끝날 때까지 반복
        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 = current.next;
        }

        // 3. 남은 노드들을 이어붙이기
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        // 4. 더미 노드의 다음 노드(실제 시작점)를 반환
        return dummy.next;
    }
}