[leetcode] 21. Merge Two Sorted Lists

문제

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 

풀이

list에 대한 기본 구현을 묻는 문제이다. Merge Sort에 대한 기본적인 지식이 있다면 어렵지 않게 풀수 있다.

각각의 list가 정렬되어 있으므로, 가장 작은 숫자는 l1[0](그냥 array notation으로 쓰겠다.)과 l2[0]중에 작은 것이 된다.

그 후 그 작은걸 list에서 제거하면, 다시 처음과 같은 상황이 되고 l1[0]과 l2[0]중에 작은 숫자를 찾으면 된다.

이를 계속해서 반복하여, 제거되는 숫자들을 모으면 정렬된 리스트를 만들 수 있다.

 

Time Complexity : $O(|l1|+|l2|)$

 

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
};