[자바스크립트/알고리즘] LeetCode - 정렬된 두 리스트 합치기

[문제] 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list.

The list should be made by splicing together the nodes of the first two lists.

 

[예시]

Input	Output
l1 = [1,2,4], l2 = [1,3,4]	[1,1,2,3,4,4]
l1 = [], l2 = []	[]
l1 = [], l2 = [0]	[0]

 

[풀이]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(!l1 || !l2) return(l1 ? l1 : l2);
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

풀다가 막혀서 해설에서 힌트를 얻었다.

재귀로 풀 생각을 못 했는데 너무 간단해서 이 해설을 참고하였다.

 

우선, l1과 l2가 빈 리스트라면 출력도 []이다. (예시2)

그리고 l1 혹은 l2가 빈 리스트이고, 나머지 리스트에 숫자 하나가 들어가 있으면 출력은 그 숫자이다. (예시3)

이 두가지를 합친게 2번째 줄이다. (주석 제외)

 

그리고 나머지 풀이를 보면 꽤 간단하다.

l1의 val보다 l2의 val이 더 큰 경우, l1의 next는 l1의 next와 l2를 다시 비교하게 된다. (재귀)

그리고 l1을 반환하게 된다.

 

l2의 val보다 l1의 val이 크거나 같은 경우도 위의 순서와 마찬가지다.