[LeetCode] Merge Two Sorted Lists (JS)

문제

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

입출력 예

Example

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

접근

두개의 리스트의 크기 비교를 하면서 하나의 리스트에 merge하는 문제인데,

1. 우선 new ListNode로 새로운 노드를 만들어주고 이를 새 변수 change에 할당한다.
2. 입출력으로 들어온 두개의 리스트의 head의 value부터 비교하여 change의 next에 넣는다. 주어진 list들은 그 next값으로 재 할당한다. 이때 while을 사용하는데 조건은 l1과 l2가 둘다 null이 아닐때로 한다.
3. 하나의 노드가 change의 next로 들어가면 change = change.next;로 값을 변경시켜준다.
4. 만일 while문을 탈출하고 l1과 l2 둘 중 여전히 null이 아닌 값이 있다면 이제껏 merge한 리스트인 change의 next에 추가한다.
5. change.next을 return

풀이

/**
 * Definition for singly-linked list.
 * 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) {
    let mergedlist = new ListNode
    let change = mergedlist;
    
    
    while(l1 !== null && l2 !== null){
        //두개의 리스트의 크기 비교를 하면서 하나의 리스트에 merge
        if(l1.val <= l2.val){
            change.next = l1;
            l1 = l1.next;
        }else{
            change.next = l2;
            l2 = l2.next;
        }
        // change값 계속 변경
        change = change.next;
        console.log('check change',change)
        console.log('check mergedlist',mergedlist)
        
    }
    
    if(l1 !== null){
        change.next = l1;
    }
    if(l2 !== null){
        change.next = l2;
    }
    
    return mergedlist.next;
    
};

+) mergedlist도 값이 같이 변하는 이유

let node = new ListNode;
let testnode = node;
node === testnode; //true라는 당연한 결과를 확인할 수 있습니다.

//그래서 할당한 testnode에 next를 추가하면 주소참조이기 때문에
testnode.next = new ListNode(1);
testnode; // ListNode {val: 0, next: ListNode}
//기존의 node역시 next가 추가되는 사실을 확인 할 수 있습니다.
node; //ListNode {val: 0, next: ListNode}

// 그러나 오늘 작성한 위의 코드에서는 
// change = change.next;을 통해 change라는 값을 계속 next로 바꾸었는데요,
// 마지막 return 값으로 change.next로 하면 제출 실패하고 mergedlist.next로 하면 제출이 성공합니다.
// 이는 어찌됐는 종국에는 change와 mergedlist값이 다르다는 뜻인데요...?
// 그 이유는 아래와 같습니다. 위 코드와 마찬가지로 아래와 같이 콘솔을 확인하면
testnode = testnode.next;
node === testnode; // false로 다른 값을 가지게됩니다. 대신...

// testnode는 원래 node의 주소참조를 하고 있었는데, 
// testnode = testnode.next로 인해서 node.next의 주소참조로 바뀌게 되는 것 입니다.
node.next === testnode; //true

// 그래서 testnode.next를 추가하면 node.next.next에 참조를 하고 있기 때문에 node.next.next에도 역시 추가가 되는 것 입니다...! 
testnode.next = new ListNode(2);
testnode.next // ListNode {val: 2, next: null}
node.next.next // ListNode {val: 2, next: null}
node.next.next === testnode.next // true

// 변경해도 적용 됩니다
testnode.next = new ListNode(4)
testnode.next // ListNode {val: 4, next: null}
node.next.next === testnode.next // true

끝