Merge Two Sorted Lists

해설

문제에서 특정 자료구조를 제공함

//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) {}
};

이 자료구조를 이용해서 문제를 풀어야 함

문제의 유의사항은 다음과 같음

1. 두 연결리스트의 크기는 다름
2. 반환값은 연결리스트의 head를 반환해야함
3. 주어지는 두 연결리스트는 오름차순 정렬된 리스트임

즉, 포인터를 가지고 놀아야한다는것임

먼저

ListNode* head = nullptr;
ListNode* last = nullptr;

이렇게 head와 last를 구분지어놓는다.
head를 반환할거고, last는 head에서부터 이어가며 포인터가 계속 바뀔 객체임

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* head = nullptr;
        ListNode* last = nullptr;

        while(list1 != nullptr || list2 != nullptr)
        {
            ListNode* t;

            int i1 = list1 == nullptr ? 101 : list1->val;
            int i2 = list2 == nullptr ? 101 : list2->val;

            if(i1 < i2)
            {
                t = list1;
                list1 = list1->next;
            }
            else
            {
                t = list2;
                list2 = list2->next;
            }

            if(head == nullptr)
            {
                head = t;
                last = head;
            }
            else
            {
                last->next = t;
                last = last->next;
            }
        }

        return head;
    }
};

잘 보면 while문에서 주어지는 두 리스트의 nullptr을 체크함

그리고, 최대값인 100을 초과하는 값으로 i1, i2라는 값을 초기화함

i1와 i2를 비교하고, t포인터를 해당 리스트로 바꿔줌

첫 값일때는 head가 nullptr일테니
head 포인터를 t로 바꿔주고, last 포인터는 head로 바꿔줌

그다음부터는 last 포인터를 계속 바꾸면서 수정함

소감

이런 연결리스트는 처음 써봐서 좀 당황...
시간 오래걸림

근데 풀다보니 해결됨