[LeetCode] 21. Merge Two Sorted Lists

LeetCode - 21. Merge Two Sorted Lists 알고리즘 문제 풀이

분류

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

풀이

감소하지 않는 숫자로 이루어진 리스트 l1과 l2가 주어질 때, 두 리스트를 합하여 감소하지 않는 숫자로 이루어지는 하나의 리스트를 반환하는 문제이다.

• 새로운 리스트를 만들 때 l1, l2의 숫자(val)를 비교하여 작은 숫자를 먼저 추가한다.
• 사용된 리스트 포인터가 다음(next) 위치를 가리키도록 변경한다.
• nullptr이 아닐 때까지 반복한다.

구현의 편의상 처음에 val(0) 값을 갖는 노드를 만들어주고, 반환하기 전에 head의 첫 번째 노드를 제거해준다.

소스 코드

/**
 * 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 *head = new ListNode();
        ListNode *p = head;
        
        ListNode *a = l1;
        ListNode *b = l2;
        
        while (a != nullptr && b != nullptr) {
            if (a->val < b->val) {
                p->next = new ListNode(a->val, a->next);
                a = a->next;
            }
            else {
                p->next = new ListNode(b->val, b->next);
                b = b->next;
            }
            p = p->next;
        }
        
        while (a != nullptr) {
            p->next = new ListNode(a->val, a->next);
            a = a->next;
            p = p->next;
        }
        while (b != nullptr) {
            p->next = new ListNode(b->val, b->next);
            b = b->next;
            p = p->next;
        }
        
        ListNode *res = head->next;
        delete head;
        
        return res;
    }
};