LeetCode / Linked List / 21번 / Merge Two Sorted Lists / JS

< 문제 바로가기 >

Merge Two Sorted Lists - LeetCode

 

< 문제 간단정리 >

주어진 두개의 Linked List를 하나의 List로 Merge하여 오름차순으로 정렬하면 되는 문제이다.

 

/**
 * 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) {
    let mergedList = { val: null, next: null };
    let head = mergedList;

    while(list1 && list2) {
        if(list1.val < list2.val) {
            mergedList.next = list1;
            list1 = list1.next;
        }
        else {
            mergedList.next = list2;
            list2 = list2.next;
        }
        mergedList = mergedList.next;
    }

    mergedList.next = list1 || list2;

    return head.next;
};

---

처음에는 list1과 list2가 단순히 배열로만 되어있는줄 알고 단순히 두 배열을 합친 후 반환하면 된다고 생각했다.

하지만 반환 값 역시 주어진 리스트의 형태로 반환을 해야한다.

그래서 주어진 list의 구조가 궁금했었는데, console.dir(list1)을 해보면 다음과 같이 나온다.

ListNode {
  val: 1,
  next: ListNode { val: 2, next: ListNode { val: 4, next: null } }
}

 

val은 현재 가리키고 있는 값이고, next에는 다음 Node의 val과 그 다음 next가 들어있다.

 

따라서 위와 같은 형태로 mergedList를 생성해주었고, null로 초기화를 해주었다.

그리고 list1.val과 list2.val을 비교해서 작은쪽을 mergedList.next와 연결시켜주었고, list1은 list1.next, 즉 다음 노드로 연결시켜주었다. 한마디로 작은 값인 노드를 mergedList와 연결시켜주고, 원래 연결되어있던 곳과 연결을 끊는것이다.

그렇게 되면 마치 mergedList에 값이 들어간것처럼 된다.

 

순서는 아래와 같이 된다.

 

 

마지막에 list1의 4가 연결되지 않고 list1에 남은채로 반복문이 끝나게 된다.

따라서 위와 같이 남은 노드가 있을 경우도 있기 때문에, 만약 남아있는 노드가 있다면 반복문을 마치고 전부 mergedList에 연결해주면 된다.