[leetCode] 21. Merge Two Sorted Lists (Easy) 풀이

❓ 문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

정렬된 두 개의 링크 리스트 list1과 list2의 헤드가 제공됩니다.

두 리스트를 하나의 정렬된 리스트로 병합하세요. 리스트는 처음 두 리스트의 노드를 연결하여 만들어야 합니다.

병합된 링크 리스트의 헤드를 반환하세요.

Example 1

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

Example 2

Input: list1 = [], list2 = []
Output: []

Example 3

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

❗ 내 답변

문제 자체를 이해 못해서 풀지 못했다.
링크드 리스트의 개념과 그에 대한 코드 지식이 부족해서 그런 것 같다.

콘솔을 찍었을 때 배열이 나오길래 concat 해서 sort 해주려고 했었다;;;
그런데 forEach 등으로 반복을 돌릴 수 없었다.
어떤걸 반환을 해줘야하는 지도 모르겠어서, 결국 다른 분의 답을 보게 되었다.

/**
 * 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) {
    var mergedHead = { val : -1, next : null },
        crt = mergedHead;
    while(l1 && l2) {
        if(l1.val > l2.val) {
            crt.next = l2;
            l2 = l2.next;
        } else {
            crt.next = l1;
            l1 = l1.next;
        }
        crt = crt.next;
    }
    crt.next = l1 || l2;

    return mergedHead.next;
};

Discuss 게시판에서 가장 상단에 있던 답이다.

 

mergedHead를 정의해줬고, crt에 mergeHead 를 담았다.
crt는 아마 current(현재 값)의 줄임말 인 듯 하다.

 

l1 과 l2 가 유효하다면 반복을 돈다.
아마 반복을 돌면서 비워진다거나? 하는 유효하지 않은 상태가 되는 것 같다.

 

l1의 val 이 l2의 val 보다 크다면,
crt의 next는 l2가 된다.
l2는 l2의 next가 된다.

작은 값 부터 큰 값을 가리키는 링크드 리스트가 되어야하기 때문에 crt에
작은 l2를 담는 것이다.

 

l1의 val 이 l2의 val 보다 크지 않다면,
crt의 next는 l1가 된다.
l1는 l1의 next가 된다.

 

반복 한바퀴를 돌고나면, crt는 crt의 next가 된다.

반복이 끝나고 나면 l1또는 l2 중 유효한 것을 crt.next에 담는다.

둘 중 길이가 좀 긴 리스트의 나머지 노드들이 이렇게 담기게 되겠다는 걸 예측할 수 있다.

그리고 mergedHead의 next를 리턴한다.

mergedHead는 지금까지 선언된 이 후에 한번도 언급 되니 않았는데 어떻게 반환의 주체가 될 수 있는 거지?
그 이유는 기존 값에 영향을 주게되는 얕은 복사 때문인 듯 하다.

 

주어진 그림을 예로 들어보면,

초기에
l1은 { val: 1, next: { val: 2, next: {...} } }
l2은 { val: 1, next: { val: 3, next: {...} } }인 상태인 것이다.

 

첫번째 반복
둘 다 유효한 상태이기 때문에 반복을 돌게 된다.

l1.val 인 1과 l2.val인 1을 비교했을 때 l1.val > l2.val를 만족하지 않기 때문에
crt.next는 l1인 { val: 1, next: { val: 2, next: {...} } } 이 되고,
l1은 l1의 next인 { val: 2, next: { val: 4, next: null } } 이 된다.

 

아까 아마 반복을 돌면서 비워진다거나? 하는 유효하지 않은 상태가 되는 것 같다. 라고 했었는데,
이렇게 보니 가장 마지막 노드에 도달해 null이 오는 순간이 바로 유효하지 않은 상태 인 것 같다.

 

한 반복을 돌았으니 crt는 crt.next가 된다.

즉, 반복 한 번을 돈 지금까지,
l1은 { val: 2, next: { val: 4, next: null } }
l2는 { val: 1, next: { val: 3, next: {...} } }
crt는 { val: 1, next: { val: 2, next: {...} } }

 

두번째 반복
l1, l2 둘 다 유효한 상태이기 때문에 한번 더 반복을 돈다.
l1,val 인 2와 l2.val인 1을 비교했을 때 l1.val > l2.val를 만족하기 때문에
crt.next는 l2인 { val: 1, next: { val: 3, next: {...} } }이 되고,
l2는 l2의 next인 { val: 3, next: { val: 4, next: null }}가 된다.

 

한 반복이 돌았으니 crt는 crt.next가 된다.

 

즉, 두번째 반복을 돈 지금까지,
l1은 { val: 2, next: { val: 4, next: null } }
l2는 { val: 3, next: { val: 4, next: null }}
crt는 { val: 1, next: { val: 3, next: {...} } }

 

세번째 반복
l1, l2 모두 유효하니 한번 더 반복을 돈다.
l1.val인 2와l2.val 인 3을 비교했을 때 l1.val > l2.val를 만족하지 않기 때문에
cur.next는 l1인 { val: 2, next: { val: 4, next: null } }이 되고,
l1는 l1의 next인 { val: 4, next: null }이 된다.

 

한 반복을 돌았으니 crt는 crt.next가 된다.

즉, 반복을 세 번 돈 지금까지,
l1은 { val: 4, next: null }
l2는 { val: 3, next: { val: 4, next: null }}
crt는 { val: 2, next: { val: 4, next: null } }가 된다.

 

네번째 반복
l1, l2 모두 유효하니 한번 더 반복을 돈다.
l1.val인 4와 l2.val인 3을 비교 했을 때 l1.val > l2.val를 만족하기 때문에
crt.next는 l2 인 { val: 3, next: { val: 4, next: null }}가 되고,
l2는 l2의 next인 { val: 4, next: null } 가 된다.

 

한 반복이 돌았으니 crt는 crt.next가 된다.

즉, 네번째 반복을 돈 지금까지,
l1은 { val: 4, next: null }
l2는 { val: 4, next: null }
crt는 { val: 3, next: { val: 4, next: null }} 가 된다.

 

다섯번째 반복
l1, l2 모두 유효하니 한번 더 반복을 돈다.
l1.val인 4와 l2.val인 4을 비교 했을 때 l1.val > l2.val를 만족하지 않기 때문에
cur.next는 l1인 { val: 4, next: null }이 되고,
l1는 l1의 next인 null이 된다.

 

한 반복이 돌았으니 crt는 crt.next가 된다.

즉, 다섯번째 반복을 돈 지금까지,
l1은 null
l2는 { val: 4, next: null }
crt는 { val: 4, next: null } 가 된다.

 

l1이 null이 되어 while의 조건문 l1 && l2 가 유효하지 않기 때문에
반복문을 빠져나온다.

crt.next는 l1이 null이니 l2인 { val: 4, next: null }가 될 것이다.
최종적으로 mergedHead.next를 반환하면서 종료된다.

mergedHead.next는
{ val: 1, next: { val: 1, next: { val: 2, next: { val: 3, next: { val: 4, next: { val: 4, next: null } } } } } 가 되는 것이다.

❗ Runtime이 가장 빨랐던 답변과 비교

위 답변과 같았다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * 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) return list2;
    if (!list2) return list1;

    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }

};

재귀함수를 사용했다.

list1 이 유효하지 않으면 list2를 반환하고,
list2 가 유효하지 않으면 list1을 반환한다.

 

list1.val이 list2.val 보다 작으면,
list1.next는 mergeTwoLists(list1.next, list2)가 된다.
그리고 list1을 반환한다.

 

list1.val이 list2.val 보다 작지 않으면,
list2.next는 mergeTwoLists(list1, list2.next)가 된다.
그리고 list2을 반환한다.

 

주어진 예제로 확인해보자.

 

첫번째 반복(재귀)

 

list1.val < list2.val 조건이 둘 다 1 이기 때문에 성립하지 않는다.
따라서 list2.next는 mergeTwoLists(list1, list2.next)가 된다.

 

두번째 반복(재귀)

list1.val < list2.val 조건이 list1.val은 1, list2.val은 3 이기 때문에 성립한다.
따라서 list1.next 는 mergeTwoLists(list1.next, list2)가 된다.

 

세번째 반복(재귀)

list1.val < list2.val 조건이 list1.val은 2, list2.val은 3 이기 때문에 성립한다.
따라서 list1.next 는 mergeTwoLists(list1.next, list2)가 된다.

 

네번째 반복(재귀)

list1.val < list2.val 조건이 list1.val은 4, list2.val은 3 이기 때문에 성립하지 않는다.
따라서 list2.next는 mergeTwoLists(list1, list2.next)가 된다.

 

다섯번째 반복(재귀)

list1.val < list2.val 조건이 list1.val은 4, list2.val은 4 이기 때문에 성립하지 않는다.
따라서 list2.next는 mergeTwoLists(list1, list2.next)가 된다.

 

여섯번째 반복(재귀)
list1.val < list2.val 조건에 도달하기 전에, list2 가 null이다.
때문에 list1을 반환하며 끝나게 된다.

 

💡 개선 방안

(내가 푼 답이 없어서... 개선이라기엔 애매하지만)
반복문과 링크드 리스트에 대한 구조와 개념을 잘 파악하고 활용해야겠다.