[LeetCode] 21. Merge Two Sorted Lists

[LeetCode] 21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

포인터가 나오다니 신기하다.

오랜만에 포인터를 사용하니 단순한 방법을 두고 뱅뱅 돌아서 구현했다가, 다른 풀이를 보고 아차 싶어 다시 풀었다.

두 sorted list의 노드를 처음부터 하나씩 서로 비교하여 값이 더 작은 노드를 새로운 list의 next로 지정하고, 원본 list에서의 next 노드를 다음번에 확인할 노드로 지정한다.

l1과 l2중 어느 하나라도 노드 탐색이 끝나면 노드가 남은 list의 나머지부분을 그대로 갖다 붙이면 된다.

/** * 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* l1, ListNode* l2) { ListNode* newRoot = new ListNode; ListNode* newNode = newRoot; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val){ newNode->next = l1; l1 = l1->next; } else { newNode->next = l2; l2 = l2->next; } newNode = newNode->next; } if (l1 != NULL) newNode->next = l1; else if (l2 != NULL) newNode->next = l2; return newRoot->next; } };

from http://gokong.tistory.com/49 by ccl(A) rewrite - 2021-10-18 22:00:56