21. Merge Two Sorted Lists

정렬된 list1, list2 head가 주어진다.
두개를 합해서 정렬된 하나의 리스트를 만들어야한다.
Return the head of the merged linked list. => head를 return하라.

1. 두 리스트의 head가 모두 비어있을 때 빈 배열
2. 두 리스트 중 하나라도 있다면, 두 리스트의 head가 모두 빌 때 까지 while

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */

틀림

var mergeTwoLists = function(list1, list2) {
    if (!list1 && !list2) return [];
    
    let head = null;
    
    const mergeList = (first, second, head) => {
        if (!first && !second) return head;
        
        if (first.val < second.val) {
            head = first.val;
            head.next = second.val;
            console.log('1:', head, head.next)
            mergeList(first.next, second.next, head);
        } 
        if (first.val >= second.val) {
            head = second.val;
            head.next = first.val;
            console.log('2:', head, head.next)
            mergeList(first.next, second.next, head);
        }
    }
    mergeList(list1, list2, head);
};

둘 중 하나만 선택되어 나오고, 리스트로도 나오지 않음.

정답) 재귀

---

var mergeTwoLists = function(list1, list2) {
    
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2); 
        // console.log('list1', list1 );
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        // console.log('list2', list2 );
        return list2;
    }
};

---

더 작은 요소를 가지고 있는 링크드리스트를 헤드로 삼고, 헤드로 삼은 링크드리스트의 다음 노트와, 헤드가 되지 못한 링크드리스트 두 리스트를 다시 함수에 넣는다.

https://leetcode.com/problems/merge-two-sorted-lists/submissions/