[Easy] 21. Merge Two Sorted Lists

문제

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.

 

예시

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.

 

해결 과정

처음 아이디어는 mergeList = []; 를 생성하여 node를 넣고 return 하는 거였는데, mergeList의 Type이 ListNode가 아니라 TypeError가 떴다...

그래서 discuss를 몇 개 살펴보니 node를 반환해야하는 것을 깨닫고 코드를 다시 고쳤다.

 

• 우선 새로운 mergeList의 head를 생성한다.
• 값을 저장한 curr 변수에 head를 할당한다. (시작점)
• list1이나 list2가 null이 될 때까지 while loop를 순회한다.
  • list1 < list2 일 때, curr.next를 list1로 지정하고 list1를 다음 순서로 옮긴다.
  • list2 < list1 일 때, curr.next를 list2로 지정하고 list2를 다음 순서로 옮긴다.
  • if문을 수행하고 나면 curr도 다음 순서로 옮긴다.
• while문을 빠져나오면 list1이나 list2가 null인데, 둘 중 하나에 값이 남아있을 수 있으니 남은 node를 curr.next에 담는다.
• 완성된 연결 리스트의 head.next를 반환한다.

 

해결 코드

/**
 * 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 head = new ListNode(0, null);
    let curr = head;
    
    while(list1 && list2){
        if(list1.val < list2.val){
            curr.next = list1;
            list1 = list1.next;
        }else{
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    
    curr.next = list1 || list2;
    
    return head.next;
    
};