Leetcode - 21. Merge Two Sorted Lists

soopsaram·2022년 5월 12일
0

멘타트 훈련

목록 보기
21/129

문제

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

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;
    }
}
profile
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)

0개의 댓글