[leetcode][TS] 21. 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.

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

 

예시

 

코드

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

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if(list1 === null){
        return list2;
    }
    
    if(list2 === null){
        return list1;
    }
    
    const newNode = new ListNode();
    let dummy = newNode;
    
    while(list1 && list2){
        if(list1.val < list2.val){
            dummy.next = list1;
            list1 = list1.next;
        }else{
            dummy.next = list2;
            list2 = list2.next;
        }
        dummy = dummy.next;
    }
    
    if(list1) {
        dummy.next = list1;
    }
    else if(list2){
        dummy.next = list2;
    }
    
    return newNode.next;
    
};

먼저 결과를 저장할 노드를 생성하고,  한 칸씩 이동하면서 노드에 값을 넣어주어야 하기 때문에 그런 역할을 할 dummy 노드를 만든다. list1과 list2의 value 값을 비교해 더 작은 값을 가진 노드를 dummy 노드의 next에 넣어준다. 그 후 작은 값을 가진 노드의 리스트를 다음 노드로 바꾸어준다. 그 후, dummy 노드도 next로 바꾸어준다. list1이나 list2 둘 중 하나라도 null이면 while문에서 빠져나오므로, 빠져나왔을 때 list1이나 list2에 남은 노드가 있을 수 있다. 따라서 list1과 list2를 확인해 확인하지 않은 노드가 있으면 dummy 노드의 next로 넣어준다. 

초기에 만든 노드는 인자로 아무 것도 넣어주지 않았기 때문에 value가 0인 노드가 들어가 있다. 따라서, newNode의 next를 리턴해준다.