주어진 두 정렬된 링크드 리스트를 합치기(정렬된 상태로)
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
"재귀함수는 정답을 리턴한다".
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;
}
}