Leetcode - 21. Merge Two Sorted Lists

문제

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

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

해결 (recursive)

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

/**
 * 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;
    }
}