[LeetCode - C] 21. Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

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]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

---

Solution 1

 

그냥 무지성으로 해결했다.

 

처음에는 l1 -> next -> val >= l2 > val을 조건으로

 

l1 next의 val이 l2 > val 보다 크거나 같으면

 

l1과 l1 -> next 사이에 들어가면 되므로 그에 따라

 

temp 이용하여 이어주는 작업을 했는데

 

예외 케이스가 너무 많이 생겼다.

 

1. l1 l2 둘 다 null일 경우

 

2. l1만 null일 경우

 

3. l2만 null일 경우

 

4. l1 l2 둘 다 한 개의 노드만 가질 경우

 

5. l1의 첫 번째 노드의 val이 l2의 첫 번째 노드의 val보다 클 경

 

6. 5의 역

 

이를 다 처리하다 보니 코드가 너무 길어졌다.

 

출제자가 원했던 방식은 아닐 것 같은데

 

내가 구조체의 포인터를 다루는 게 익숙지 않아서 이대로 진행했다.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode *l1;
    struct ListNode *l2;
    struct ListNode *temp;
    
    l1 = list1;
    l2 = list2;
    if (!l1 && !l2)
        return (0);
    if (!l1)
        return (l2);
    if (!l2)
        return (l1);
    if (!l1 -> next && !l2 -> next)
    {
        if (l1 -> val > l2 -> val)
        {
            l2 -> next = l1;
            return (list2);
        }
        else
            l1 -> next = l2;
        return (list1);
    }
    if (l1 -> val < l2 -> val)
    {
        while (l1 -> next && l2)
        {
            if (l1 -> next -> val >= l2 -> val)
            {
                temp = l1 -> next;
                l1 -> next = l2;
                l2 = l2 -> next;
                l1 -> next -> next = temp;
            }
            l1 = l1 -> next;
        }
        if (!l1 -> next)
        {
            l1 -> next = l2;
        }
        return (list1);
    }
    else
    {
        while (l2 -> next && l1)
        {
            if (l2 -> next -> val >= l1 -> val)
            {
                temp = l2 -> next;
                l2 -> next = l1;
                l1 = l1 -> next;
                l2 -> next -> next = temp;
            }
            l2 = l2 -> next;
        }
        if (!l2 -> next)
        {
            l2 -> next = l1;
        }
        return (list2);
    }

}

---

Solution 2

(인터넷 참고)

 

재귀를 이용한 방법

 

재귀 호출하여 맨 끝에서부터 하나씩 이어준다.

 

처음 해결했던 것과 다르게 맨 끝에서부터

 

이어 주기 때문에 temp가 필요 없다.

 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    if (list1 -> val <= list2 -> val)
    {
        struct ListNode *node = mergeTwoLists(list1 -> next , list2);
        list1 -> next = node;
        return list1;
    }
    else
    {
        struct ListNode *node = mergeTwoLists(list1 , list2 -> next);
        list2 -> next = node;
        return list2;
    }   
}

---

총평

 

풀면서 뭔가 코드가 길어져서 이게 맞나?라는 생각이 들었는데

 

일단 시작한 거 완성은 했다.

 

이후 다른 사람들 풀이한 것 찾아보다가

 

재귀 이용해 해결한 것을 발견했다.

 

재귀는 참 많이 쓰이는데 나는 아직 잘 못한다는 게 너무 아쉽다.