merge-two-sorted-lists

설명

- Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

- 두개의 정렬된 연결리스트들을 합쳐진 리스트로 반환하라. 

Merge two sorted link- ed lists and return it as a

 

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1,1,2,3,4,4]

 

Example 2:

Input: l1 = [], l2 = []

Output: []

 

Example 3:

Input: l1 = [], l2 = [0]

Output: [0]

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    const head = new ListNode();
    let cur = head;

    while (l1 && l2) {
        if (l1.val > l2.val) {
            cur.next = l2;
            cur = cur.next;
            l2 = l2.next;
        }
        else {
            cur.next = l1;
            cur = cur.next;
            l1 = l1.next;
        }
    }
    if (l1) cur.next = l1;
    if (l2) cur.next = l2;

    return head.next;
};

설명

head라는 새로운 연결리스트를 만들어주고 head부분을 참조하는 cur변수를 만들어준다.

그리고 l1과 l2가 끝날때까지 반복을 해주는데 l1과 l2의 값들중에서 정렬된값을 넣어줘야하기때문에 조건을 걸어서 l1의 값이 더 크면 l2값을 넣어주고 그렇지않으면 반대로 넣어주는식으로 정렬된채로 값을 cur에 넣어준다.

조건문안에 보면

cur.next = l2 에서는 head.next = l2랑 같다. 그리고 head가 head.next를 포함해도 cur는 여전히 head와 같다.

cur = cur.next 에서는 더이상 cur는 head와 같지않지만 head.next와는 같다.

 

while문이 끝나고 마지막 l1,l2중에 더 긴 리스트가 있으면 나머지를 채워넣는다.