난이도: EASY
문제
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.
시도 1
/**
* 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) {
if(list1.isEmpty() && list2.isEmpty()) return null;
list1.addAll(list2);
System.out.println(list1.toString());
Collections.sort(list1); // 오름차순 정렬 (작은 값 → 큰 값)
return list1;
}
}※ ListNode는 일반적인 리스트가 아닌 단순 연결 리스트(Singly Linked List)이므로 List의 메서드를 사용할 수 없다.
단순연결리스트를 이론적으로는 알았는데(방통대 시절 배움) 실제로 사용한 적이 없어서 , 일반 리스트인 것 마냥 풀어서 컴파일에러 파티.
그래서 챝지선생님한테 쉽게 설명 좀 해달라고 부탁드렸다....^^.... 설명이 생각보다 길어서 접었다.
📌 단순 연결 리스트 (Singly Linked List)란?
👉 한 방향으로만 연결된 데이터 구조
단순 연결 리스트(Singly Linked List)는 각 노드(Node)가 다음 노드만을 가리키는 구조로 되어 있습니다.
1️⃣ 단순 연결 리스트의 구조
📌 기본적인 개념:
- 각 노드(Node) → 데이터를 저장하는 값(val) + 다음 노드를 가리키는 포인터(next)
- 마지막 노드(tail)의 next → null (더 이상 다음 노드가 없음)
🔹 예제
아래와 같은 연결 리스트가 있다고 가정해 봅시다.
각 노드는 값과 다음 노드를 가리키는 포인터를 가지고 있습니다.
| 노드(ListNode) | 값(val) | 다음 노드(next) |
| 첫 번째 노드 | 1 | 2 |
| 두 번째 노드 | 2 | 3 |
| 세 번째 노드 | 3 | 4 |
| 네 번째 노드 | 4 | null (끝) |
2️⃣ 단순 연결 리스트의 특징
✅ 배열(Array)와 다른 점
| 특징 | 배열(Array) | 단순 연결 리스트(Singly Linked List) |
| 크기 변경 가능 여부 | 고정 크기 (변경 불가능) | 동적으로 크기 조절 가능 |
| 삽입/삭제 속도 | 느림 (O(n), 요소를 밀어야 함) | 빠름 (O(1), next만 변경하면 됨) |
| 임의 접근(Random Access) | 가능 (arr[index]) | 불가능 (처음부터 next 따라가야 함) |
| 메모리 사용량 | 적음 | 추가적인 포인터(next)가 필요 |
3️⃣ 단순 연결 리스트의 기본 연산
📌 (1) 노드 삽입
새로운 값을 리스트에 추가하는 방법입니다.
// ListNode 클래스
class ListNode {
int val;
ListNode next; // 다음 노드를 가리키는 포인터
// 생성자
ListNode(int val) { this.val = val; }
}
//------------------------------------------------
// 새로운 노드 추가
ListNode head = new ListNode(1); // 첫 번째 노드 (head)
head.next = new ListNode(2); // 두 번째 노드
head.next.next = new ListNode(3); // 세 번째 노드결과: 1 → 2 → 3 → null
📌 (2) 노드 삭제
특정 노드를 삭제하는 방법입니다. (예: 2 삭제)
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
// 2를 삭제
head.next = head.next.next;결과: 1 → 3 → null
✅ 삭제는 next 포인터만 변경하면 되므로 빠름(O(1))
📌 (3) 리스트 출력
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " -> ");
temp = temp.next;
}
System.out.println("null");출력 결과: 1 -> 2 -> 3 -> null
4️⃣ 단순 연결 리스트 vs 배열 차이점 정리
| 특징 | 배열(Array) | 단순 연결 리스트(Singly Linked List) |
| 데이터 접근 | O(1) (인덱스로 접근 가능) | O(n) (처음부터 next 따라가야 함) |
| 삽입/삭제 속도 | O(n) (이동 필요) | O(1) (next만 변경) |
| 메모리 사용량 | 적음 | 더 큼 (next 포인터가 필요) |
| 크기 조절 | 불가능 (고정) | 가능 (동적 추가 가능) |
✅ 정리
- 단순 연결 리스트는 각 노드가 다음 노드만을 가리키는 데이터 구조
- 배열보다 삽입/삭제가 빠르지만, 특정 위치에 접근하는 속도가 느림
- 배열과 다르게 크기 제한 없이 동적으로 크기 조절 가능
- 자주 변경되는 데이터 구조(삽입/삭제가 많은 경우)에 적합
나의 최종 제출 답안:
이라고는 썼지만 잘몰라서 챗지한테 단계별로 설명을 요구하며 풀었...풀었다기보단 그냥 챗지가 풀고 내가 물어본 내용 정리 정도...?
/**
* 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) {
if(list1 == null && list2 == null) return null;
ListNode dummy = new ListNode(-1); // 더미 노드 생성
//tail을 더미 노드로 설정 (병합된 리스트의 끝)
ListNode tail = dummy; // tail 포인터 설정
// 두 리스트 모두 노드가 남아있는 동안 반복
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
// list1의 값이 더 작다면,
tail.next = list1; // tail의 다음 노드로 list1을 연결
list1 = list1.next; // list1을 다음 노드로 이동
} else {
// list2의 값이 더 작거나 같다면,
tail.next = list2; // tail의 다음 노드로 list2를 연결
list2 = list2.next; // list2를 다음 노드로 이동
}
tail = tail.next; // tail을 새로 추가된 노드로 이동 (포인터 업데이트)
}
// 남은 노드 처리
tail.next = (list1 != null) ? list1 : list2;
return dummy.next; // 더미 노드는 반환하지 않고 다음 노드부터 반환
}
}
그림으로 그려서 풀어봄.
이야..... 역시 기계가 풀어주는게 좋구만.....(?)
chatGPT에게 중간중간 물어봤던 것
1. 더미노드 사용 이유, ListNode dummy = new ListNode(-1); 에서 -1을 쓰는 이유
📌 ListNode dummy = new ListNode(-1);에서 -1을 쓰는 이유
더미 노드(dummy node)는 새로운 연결 리스트를 쉽게 조작할 수 있도록 도와주는 임시 노드입니다.
코드에서 -1을 사용한 이유는 더미 노드는 단순히 연결 리스트의 시작을 나타내는 역할만 하기 때문입니다.
1️⃣ 더미 노드가 필요한 이유
mergeTwoLists()에서 새로운 정렬된 리스트를 만들 때,
직접 head를 사용하면 처음 노드가 null인지 체크하는 등의 불필요한 예외 처리가 필요합니다.
🔹 더미 노드를 사용하면
- 새 리스트의 head를 따로 관리할 필요가 없음
- 첫 번째 노드를 넣을 때 별도의 if문이 필요 없음
- 새로운 노드들을 추가하는 과정이 간결해짐
2️⃣ -1을 사용하는 이유
ListNode dummy = new ListNode(-1);🔹 더미 노드의 값은 보통 어떤 값이든 상관없습니다.
다만, 유효한 값들과 구분하기 위해 -1을 사용하는 경우가 많습니다.
📌 예제: 더미 노드 없이 병합
ListNode head = null;
ListNode tail = null;
if (list1.val < list2.val) {
head = list1;
tail = list1;
list1 = list1.next;
} else {
head = list2;
tail = list2;
list2 = list2.next;
}
// 이후 while문에서 tail.next를 계속 추가...🔹 이 방식은 첫 번째 노드를 선택하는 과정에서 if문이 필요하고, head와 tail을 따로 관리해야 합니다.
더미 노드를 사용하면 이러한 초기 head 설정을 생략할 수 있습니다.
3️⃣ 더미 노드 사용 시 코드 간결화
ListNode dummy = new ListNode(-1); // 더미 노드 생성
ListNode tail = dummy; // tail 포인터 설정
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next; // tail 이동
}
// 남은 노드 처리
tail.next = (list1 != null) ? list1 : list2;
return dummy.next; // 더미 노드는 반환하지 않고 다음 노드부터 반환✅ 더미 노드를 사용하면 코드가 간결해지고, head를 따로 관리할 필요가 없어집니다.
✅ 결론
- 더미 노드는 새로운 연결 리스트를 만들 때 처음을 쉽게 관리하기 위해 사용합니다.
- 값 -1을 쓰는 이유
- 더미 노드의 값은 실제 사용되지 않음.
- 유효한 데이터와 구별되도록 의미 없는 값(-1, 0 등)을 사용.
- 어떤 값이든 상관없지만, 대부분 -1이나 0을 사용.
👉 즉, dummy 노드는 리스트를 정리하기 위한 보조 역할일 뿐이고, -1은 단순히 의미 없는 값일 뿐입니다! 🚀
2. ListNode tail = dummy 의 의미
📌 ListNode tail = dummy; 가 의미하는 것
이 부분은 새로운 병합 리스트의 "마지막 노드"를 가리킬 포인터(tail)를 초기화하는 코드입니다.
1️⃣ ListNode dummy = new ListNode(-1);
먼저, dummy 노드는 새로운 연결 리스트를 쉽게 만들기 위해 존재하는 가짜(더미) 노드입니다.
ListNode dummy = new ListNode(-1); // 값이 -1인 더미 노드 생성이렇게 하면, 연결 리스트의 시작 부분을 쉽게 찾을 수 있고, 첫 번째 노드를 삽입할 때 예외 처리를 따로 하지 않아도 됩니다.
🔹 초기 상태: dummy(-1) → null
2️⃣ ListNode tail = dummy;
ListNode tail = dummy;이 줄은 새로운 리스트에서 마지막 노드를 가리킬 포인터(tail)를 초기화하는 것입니다.
❓ dummy가 tail이 된다고?
- dummy는 new ListNode(-1) 이므로 노드 자체입니다.
- tail = dummy; 하면 tail도 dummy 노드를 가리키게 됩니다.
- 즉, tail은 병합된 리스트의 마지막 노드 역할을 하게 됩니다.
🔹 초기 상태:
dummy(-1) → null tail = dummy이제 새로운 노드를 추가할 때마다 tail.next에 연결하고, tail을 이동하면 됩니다.
3️⃣ tail.next = list1 또는 list2를 실행하면?
새로운 노드를 추가할 때 tail.next를 업데이트합니다.
tail.next = list1;
tail = tail.next;이렇게 하면 tail이 새로운 노드를 가리키게 되어 리스트가 확장됩니다.
4️⃣ tail이 업데이트되는 과정
예제: 병합하는 과정
✅ 초기 상태
dummy(-1) → null tail = dummy✅ 첫 번째 반복 (list1.val = 1, list2.val = 2)
tail.next = list1; // 1을 추가
tail = tail.next; // tail을 1로 이동
list1 = list1.next; // list1을 다음 노드(3)로 이동
//-------------------
dummy(-1) → 1 → null
tail = 1
list1: 3 → 5 → null
list2: 2 → 4 → 6 → null✅ 두 번째 반복 (list1.val = 3, list2.val = 2)
tail.next = list2; // 2를 추가
tail = tail.next; // tail을 2로 이동
list2 = list2.next; // list2를 다음 노드(4)로 이동
//--------------------
dummy(-1) → 1 → 2 → null
tail = 2
list1: 3 → 5 → null
list2: 4 → 6 → null이렇게 tail을 계속 업데이트하면서 리스트를 확장하면 최종적으로 병합된 리스트가 생성됩니다.
5️⃣ 최종 결과
✅ 병합된 리스트
마지막으로 dummy.next를 반환하면, 병합된 리스트가 정렬된 상태로 반환됩니다.
더미 노드(-1)는 필요 없으므로 dummy.next를 반환하면 최종 정렬된 리스트가 됩니다.
✅ 정리
| 코드 | 의미 |
| ListNode dummy = new ListNode(-1); | 가짜 시작 노드(dummy node) 생성 |
| ListNode tail = dummy; | tail을 더미 노드로 설정 (병합된 리스트의 끝) |
| tail.next = list1 또는 list2; | 새로운 노드를 병합된 리스트에 추가 |
| tail = tail.next; | tail을 다음 노드로 이동 (리스트 확장) |
| return dummy.next; | dummy 노드는 제외하고 병합된 리스트 반환 |
👉 tail은 처음에는 dummy를 가리키지만, 새로운 노드가 추가될 때마다 tail.next를 갱신하면서 리스트를 확장하는 역할을 합니다.
+ 추가질문) 내가 이해한 바에 따르면 tail = dummy라는건 tail의 next가 dummy의 head를 가르키는거네 맞아?
📌 ListNode tail = dummy; 의 정확한 의미
네, 맞아요!
하지만 조금 더 정확히 설명하자면, tail은 dummy 노드 자체를 가리킵니다.
즉, "tail이 dummy 노드의 head를 가리킨다"기보다는 "tail이 처음에는 dummy 노드와 같은 위치를 가리킨다" 라고 표현하는 게 더 적절해요.
3. tail.next = (list1 != null) ? list1 : list2; 상세 설명
1️⃣ 이 코드가 필요한 이유
🚀 예제
병합 중인 두 리스트(list1, list2)가 있다고 가정해 봅시다.
🔹 초기 리스트
병합 과정에서 list1과 list2의 값을 하나씩 비교하면서 tail.next를 정렬된 순서로 연결합니다.
🔹 while문 실행 후 상황
이제 list1은 null이지만, list2에는 8 → 10 → null이 남아 있음.
🔹 이제 남은 list2를 리스트에 붙여야 함!
이걸 하나씩 추가하지 않고 한 번에 연결하는 게 tail.next = (list1 != null) ? list1 : list2; 입니다.
2️⃣ 코드 분석
tail.next = (list1 != null) ? list1 : list2;- list1이 남아 있으면 list1을 tail.next에 연결
- list1이 null이라면 list2를 tail.next에 연결
🔹 예제 실행
- list1 == null 이므로
- 최종 리스트
tail.next = list2; // 즉, tail.next = 8 → 10 → null- 마지막에 dummy.next를 반환하면 완성된 병합 리스트를 얻을 수 있습니다.
3️⃣ 만약 이 코드가 없다면?
이 코드가 없다면, 남아 있는 list1 또는 list2를 추가하는 별도의 while문을 만들어야 합니다.
while (list1 != null) {
tail.next = list1;
tail = tail.next;
list1 = list1.next;
}
while (list2 != null) {
tail.next = list2;
tail = tail.next;
list2 = list2.next;
}🔹 위 코드를 tail.next = (list1 != null) ? list1 : list2; 한 줄로 간단하게 줄인 것입니다.
✅ 핵심 정리
list2동작| 상황 | list1 | list2 | 동작 |
| list1이 남아 있음 | ✅ 있음 | ❌ 없음 | tail.next = list1; |
| list2가 남아 있음 | ❌ 없음 | ✅ 있음 | tail.next = list2; |
| 둘 다 끝남 | ❌ 없음 | ❌ 없음 | tail.next = null; (변경 없음) |
👉 즉, 남아 있는 리스트를 한 번에 붙여주는 역할을 함.
✅ while문으로 하나씩 추가하지 않고, 남아 있는 전체 노드를 통째로 연결하는 방법!
'Coding Challenges > LeetCode' 카테고리의 다른 글
| [SQL50] 1148. Article Views I (0) | 2025.02.10 |
|---|---|
| [SQL50] 1683. Invalid Tweets (0) | 2025.02.10 |
| [SQL50] 595. Big Countries (0) | 2025.02.07 |
| [SQL50] 584. Find Customer Referee (1) | 2025.02.07 |
| [SQL50] 1757. Recyclable and Low Fat Products (0) | 2025.02.06 |