[LeetCode] Merge Two Sorted Lists 문제 풀이

개요

결론적으로 해당 문제를 풀지는 못했다. 하지만 따로 정리해두지 않으면 잊어버리게 되어서 기록의 목적으로 정리한 블로그이다.

Leet 코드 실제 문제 링크

Can you solve this real interview question? Merge Two Sorted Lists - You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into 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. Example 1: [https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg] 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.

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

문제 간단 설명

두개의 linkedList를 사용하여 정렬된 새로운 linkedList를 만들어내는 함수를 정의한다. 그리고 문제엔 linkedList가 non-decreasing 이라고 하는데 의미는 다음과 같다.

💡

non-decreasing의 의미

리스트의 다음 값이 이전 값보다 작지 않다. 즉, 각 항목은 이전 항목보다 크거나 같다

✅ 비내림차순인 경우:

[1, 2, 3, 4, 5] (값이 계속 커짐)

[1, 2, 2, 4, 5] (값이 같아도 됨)

[3, 3, 3, 3] (모든 값이 같아도 됨)

❌ 비내림차순이 아닌 경우:

[1, 3, 2, 4, 5] (3 다음에 2가 와서 값이 작아졌으므로 해당 안 됨)

함수를 실행해서 기대하는 결과 모습

Listnode에 대한 이해

이 문제를 풀기 위해서는 listnode에 대한 이해가 필요하다. 입력값이 [1,2,3]이라고 할 지라도 배열의 특성을 사용할 수 없기 때문이다.

이 listnode는 linkedList를 구성하는 벽돌같은 존재라고 보면되는데, 각 listnode는 값과 참조라는 두가지정보를 가지고 있다.

문제에 제시된 listnode의 구조를 확인해보면 val, next 라는 값을 사용할 수 있다. 여기서 val 이란 변수로 값을 꺼내올수 있다.

참조

next는 현재값이 아닌 다음 값들을 가져오는데 만약 list1 = [1, 2, 4] 라는 listnode에서 list1.next를 출력하면 [2,4]가 나오고, list1.next.next를 출력하면 [4]가 나온다. 그리고 연결된 값이 아니라 한 값만 가져오고 싶다면 list1.next.val로 [2]라는 값만 가져올 수 있다.

문제 해결 과정

이 문제는 결론적으로 listnode에 대한 이해와 재귀함수의 특성으로 해결할 수 있다. 문제에 명시된 listnode의 특성은 다음과 같다.

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

var mergedTwoList에는 두개의 listnode인자를 받는다.

JavaScript

var mergeTwoLists = function (list1, list2) {

list1가 존재하지 않을 때는 list2를 반환하고 list2가 없을 때는 list1을 반환해서 재귀함수의 탈출구부터 만들어 준다.

JavaScript

if (!list1) return list2;
if (!list2) return list1;

문제에 명시된 조건으로 병합하는 핵심 부분이다. 값을 비교해서 list1이 list2의 값보다 작거나 같은경우, 함수자신을 다시 호출해서 list1의 다음 요소와, list2를 병합결과를 .next에 할당하는 형태라고 보면된다. 쉽게 말해서 지금 당장은 더 작은 노드를 고르고, 나머지는 미래의 나에게 문제를 맡긴다 는 형태라고 할 수 있겠다.

JavaScript

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

결과코드

JavaScript

/**
 * 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;
    }
}