[LeetCode]두 정렬 리스트의 병합

문제

정렬되어 있는 두 연결 리스트를 합쳐라.

예제

• Example 1:
  

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

• Example 2:

Input: list1 = [], list2 = []
Output: []

• Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

코드

/**
 * 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 {
private:
    ListNode* head;
    ListNode* tail;

public:
   
    void addNode(int n)
    {
        ListNode* temp = new ListNode;
        temp->val = n;
        temp->next = NULL;
        if(head == NULL)
        {
            head = temp;
            tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
      
    }
  
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
       if (list1 == NULL && list2 == NULL)
	{
		return head;
	}
	else if (list1 != NULL && list2 == NULL)
	{
		addNode(list1->val);
		mergeTwoLists(list1->next, list2);
	}
	else if (list1 == NULL && list2 != NULL)
	{
		addNode(list2->val);
		mergeTwoLists(list1, list2->next);
	}
	else if (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			addNode(list1->val);
			mergeTwoLists(list1->next, list2);
		}
		else if (list1->val > list2->val)
		{
			addNode(list2->val);
			mergeTwoLists(list1, list2->next);
		
		}
		else
		{
			addNode(list1->val);
			addNode(list2->val);
			mergeTwoLists(list1->next, list2->next);
		}
	}
	
	return this->head;

    }
};

풀이

1.

연결리스트에 노드를 삽입할 수 있는 함수 addNode()를 만들어준다.

2.

재귀함수를 이용하여 list1과 list2가 NULL인지 아닌지 판단을하고 둘다 비어있다면 head를
리턴하여 준다.
노드가 없다면, 있는쪽을 addNode함수로 추가하여 주고 추가한 노드가 가리키는 다음노드를
재귀함수의 매개변수로 할당하여준다.
lsit1과 list2가 둘다 NULL이 아닌경우는 val값을 비교하여 작은쪽이 먼저 addNode()로 인해 head에 추가되게 해준다.

3.

마지막과정으로는 list1과 list2가 제일 마지막 노드를 가르키고, NULL을 참조하니 mergeTwoLists함수의 첫 번째 if를 true로 진입하여 작은 수 부터 정렬된
head값을 return할 것이다.

결과

Runtime 4 ms / Memory 15.6 MB
https://leetcode.com/problems/merge-two-sorted-lists/submissions/893516545/

---

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