Leetcode - 21. Merge Two Sorted Lists

문제

주어진 두 정렬된 링크드 리스트를 합치기(정렬된 상태로)

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

해결 (recursive) - O(n) / O(n)

"재귀함수는 정답을 리턴한다".
mergeTwoLists() 함수에서 list1이 더 작다면 list1->next에 정렬된 정답(mergeTwoLists(list1->next, list2)의 리턴닶)을 저장하면, list1는 최종적으로 정렬이 모두 마무리된 리스트의 head가 된다.
Base Case 는 list 가 NULL을 만났을때.

• Base Case 에 대한 직관
  리스트의 마지막에 다다르면 두가지 케이스밖에 없다. 1. list1이 null이거나, 2.list2가 null이거나, 그게 아니라면 list1, list2에 모두 아직 노드가 존재한다는 뜻이고. 그것은 base case가 아닌 recursion을 계속 해야한다는 의미.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    /* Base Case */
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
  
    /* Recursion */
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

해결 (iterative) - O(n) / O(1)

l1과 l2포인터를 비교하면서 전진 그리고 prev값을 하나씩 뒤 따르게 만듦. new head를 새로 할당하고 new head -> next를 리턴함.

   p    l1
   1 -> 4 -> 5 
 h  
   1 -> 2 -> 3 -> 6
   l2

재귀와 다르게(콜스택 사용) 추가 메모리를 사용하지 않아서 O(1) 공간복잡도를 갖는다.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *newhead = new ListNode;
        ListNode *prev = newhead;
        
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                prev->next = list1;
                list1 = list1->next;
            } else {
                prev->next = list2;
                list2 = list2->next;
            }
            prev = prev->next;
        }
        prev->next = (list1 == NULL) ? list2 : list1;
        
        return newhead->next;
    }
};