스터디 3주차 / leetcode 21번 / Merge Two Sorted Lists / JavaScript

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

Merge Two Sorted Lists - LeetCode

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.

두개의 연결 리스트가 주어지고 각 노드의 값을 비교해서 오름 차순 형태로 한 개의 연결리스트로 만들어 내는 문제였습니다. 아직까지는 자바스크립트 언어 자체에 대해서는 입문자 수준이라 자바스크립트를 사용해서 다양한 형태의 자료구조를 구현하는게 미숙해서 다른분들의 풀이를 보고 공부하고 있습니다. 이런  좋은 풀이 덕분에 JS에 대한 이해력이 좋아지고 공부가 잘되는 것 같아 상당히 만족스러웠습니다 :)

 

아래가 큰 도움이 된 풀이 링크입니다

https://leetcode.com/problems/merge-two-sorted-lists/solutions/2666187/javascript-solution-runtime-96-59-easy-to-understand/?page=2&languageTags=javascript 

JavaScript Solution | runtime > 96.59% | easy to understand - Merge Two Sorted Lists - LeetCode

 

 

ListNode라는 이름의 생성자 함수를 통해서 list1 과 list2를 만들어서 인자로 넘겨주고 있습니다.

먼저 우리는 새로운 한 개의 연결리스트를 만들어서 반환을 해줘야 하기 때문에, result라는 이름의 ListNode를 하나

생성합니다. 그리고 추가 작업들을 위해 result를 head라는 이름으로 사용하기 위해 변수 선언을 합니다. 이 result는 val값과 next값이 존재 합니다.

 

next변수를 통해서 노드들을 연결할 것인데, 그냥 연결하면 안되고 val값을 보고 작은것 먼저 연결해야겠지요.

그래서 while문 안에 조건문을 걸어줍니다. 현재 인자로 넘어온 리스트들의 노드의 val값을 보고 list1이 작으면 

우리가 만든 head의 next에 list1 노드를 넣어 연결합니다. 반대로 list2.val이 작다면 list2를 연결합니다.

그렇게 val값을 작은 것 부터 연결하다 보면 반드시 둘 중 하나의 리스트는 모두 연결이 되고 list의 next는 null을

가리킬 것입니다. 그러면 while문은 끝이납니다. 그리고 그 밑의 while문들로 아직 연결되지 못하고 남은 list의 노드들을 

연결시켜 우리가 반환할 연결리스트를 완성시킵니다. 

 

마지막 return으로 result.next를 제출하면 우리가 만든 리스트의 첫 노드를 반환하게 됩니다. (여기에는 입력 받는 리스트들 중 가장작은 val값과 그 다음 작은 val를 갖는 노드를 가리킬 next값이 존재할 것입니다)

head.next를 반환하지 않는 이유는 우리가 추가 작업들을 하면서 head가 우리가 반환할 연결리스트의 마지막 노드이기 때문에 result.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 result = new ListNode();
    let head = result;
 
    while (list1 != null && list2 != null)
    {
        if (list1.val < list2.val)
        {
            head.next = list1;
            list1 = list1.next;
        }
        else
        {
            head.next = list2;
            list2 = list2.next;
        }
 
        head = head.next;
    }
 
    while (list1 != null)
    {
        head.next = list1;
        list1 = list1.next;
        head = head.next;
    }
 
    while (list2 != null)
    {
        head.next = list2;
        list2 = list2.next;
        head = head.next;
    }
 
    return result.next;
};