문제요약:
Given two heads of sorted linked lists list1 and list2,
merge two lists into one sorted linked list and return the head of the merged list.
제약:
-100 < Node.val < 100
lists are sorted in non-decreasing order
| 예제 1 입력. | 예제 1 출력. |
| [1,2,4] [1,3,4] |
[1,1,2,3,4,4] |
| 예제 2 입력. | 예제 2 출력. |
| [5] [1,3,4] |
[1,3,4,5] |
정답코드1 (while문 사용):
비교적 복잡하고, 신경써줘야 하는 곳이 많음.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* newHead;
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* curNode;
newHead = NULL;
if (list1 == NULL)
{
newHead = list2;
return newHead;
}
else if (list2 == NULL)
{
newHead = list1;
return newHead;
}
else
{
if (list1->val <= list2->val)
{
newHead = list1;
list1 = list1->next;
curNode = newHead;
}
else
{
newHead = list2;
list2 = list2->next;
curNode = newHead;
}
}
while ((list1 != NULL) || (list2 != NULL))
{
if (list1 == NULL)
{
curNode->next = list2;
return newHead;
}
else if (list2 == NULL)
{
curNode->next = list1;
return newHead;
}
if (list1->val <= list2->val)
{
curNode->next = list1;
list1 = list1->next;
curNode = curNode->next;
}
else
{
curNode->next = list2;
list2 = list2->next;
curNode = curNode->next;
}
}
return newHead;
}
};
|
cs |
정답코드 2 (recursive solution) :
while문 사용한 solution에 비해 깔끔.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* newHead;
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL)
{
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else if (list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
|
cs |
핵심 idea:
1. list의 헤더 = list 라고 생각
2. list->next 는 남은 list1 과 list2를 통합한 list.
원본 링크: https://leetcode.com/problems/merge-two-sorted-lists/
'알고리즘 문제풀이' 카테고리의 다른 글
| [알고리즘] LeetCode 746번 "Min Cost Climbing Stairs" (C/C++) - Don 임베디드 (0) | 2022.09.28 |
|---|---|
| [알고리즘] LeetCode 1번 "Two Sum" (C/C++) - Don 임베디드 (0) | 2022.09.27 |
| [알고리즘] LeetCode 543번 "Diameter of Binary Tree" (C/C++) - Don 임베디드 (0) | 2022.09.21 |
| [알고리즘] 백준 7568번 "덩치" (C/C++) - Don 임베디드 (23) | 2022.04.22 |
| [알고리즘] 백준 1181번 "단어 정렬" (C/C++) - Don 임베디드 (14) | 2022.04.21 |
