이번에는 merge two sorted lists를 풀어봤습니다. 역시나 쉬운 예제이며, linked list
가 2개가 주어지고, 작은 순서대로 차례차례 새로운 링키드 리스트를 만드는게 목표입니다.
문제 정의

접근 방법
- 두 리스트 중 하나라도
nullptr
가 아니라면, 계속 while loop 이 돌아갑니다. 차례차례next
를 써가면서 원소의 값을 비교하고, 작은 것을 선택한 뒤 정답 리스트에 추가합니다. 단순합니다. - 만약 두 리스트 중 하나가
nullptr
인지도 체크해서 메모리 에러가 발생하지 않도록 주의합니다.
결과
확실히 쉬운 문제는 고수들이 없는건지, 답이 한정적인건지 생각보다 런타임이 빠르게 나옵니다. 메모리 사용은... 자료구조에 대해 좀 더 이해가 필요한 것 같아요.
- Runtime: 8 ms, faster than 69.55% of C++ online submissions for Merge Two Sorted Lists.
- Memory Usage: 14.9 MB, less than 15.61% of C++ online submissions for Merge Two Sorted Lists.
코드
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 | /** * 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* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* ch = new ListNode(0); ListNode* answer = ch; while (list1 != nullptr || list2 != nullptr) { if (list1 == nullptr) { // only list 2 can be added answer->next = new ListNode(list2->val); answer = answer->next; list2 = list2->next; } else if (list2 == nullptr) { // only list 1 can be added answer->next = new ListNode(list1->val); answer = answer->next; list1 = list1->next; } else { // both lists are not nullptr if (list1->val <= list2->val) { answer->next = new ListNode(list1->val); answer = answer->next; list1 = list1->next; } else { answer->next = new ListNode(list2->val); answer = answer->next; list2 = list2->next; } } } return ch->next; } }; | cs |
'Developer > C, C++' 카테고리의 다른 글
[C++] LeetCode - Remove Duplicates from Sorted Array (Hash Map) (0) | 2022.01.14 |
---|---|
[C++] LeetCode - Valid Parentheses (Stack) (0) | 2022.01.12 |
[C++] LeetCode - Longest Common Prefix (0) | 2022.01.11 |
[C++] LeetCode - Roman to Integer (Map) (1) | 2022.01.10 |
[C++] LeetCode - Add Two Numbers (Linked List) (0) | 2022.01.07 |
댓글