본문 바로가기
개발/알고리즘

[LeetCode] Merge Two Sorted Lists (javascript)

by 자몬다 2021. 2. 26.
728x90

연결 리스트 두 개를 값이 작은 순서대로 정렬하여 합친다.

두 리스트는 이미 정렬되어 있으므로, 값을 비교해서 작은 값을 새 리스트에 추가해 나가면 된다.

 

/**
 * 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) {
    // 빈 리스트가 있다면 합칠 필요가 없다.
    if(!l1) return l2;
    if(!l2) return l1;
    // 둘중에 더 작은값을 추가해서 새 리스트를 만들면 될것같군요..

    let result = new ListNode();
    result.val = undefined; // 생성시 첫 val을 0이 들어가므로.. 첫 값을 초기화해준다.
    let nl1 = l1;
    let nl2 = l2;
    
    // l1, l2 중 한쪽이라도 값이 남아있는동안 계속 반복
    while(nl1 || nl2) {
        // 한쪽만 값이 남아있는 경우 
        if(!nl1) {
            while(nl2){
                result.add(result, nl2.val);
                nl2 = nl2.next
            }
            console.log('finish', result)
            return result;
        }
        if(!nl2) {
            while(nl1){
                result.add(result, nl1.val);
                nl1 = nl1.next
            }
            console.log('finish', result)
            return result;
        }
        
        // 더 작은 값을 result에 추가
        if(nl1.val < nl2.val){
            result.add(result, nl1.val);
            nl1 = nl1.next;
        } else {
            result.add(result, nl2.val);
            nl2 = nl2.next;
        }
        console.log(nl1, nl2, result)
    }
    return result;
};

ListNode.prototype.add = (node, val) => {
    var curr;
    if(node.val === undefined){
        node.val = val;
    } else {
        curr = node;
        while(curr.next){
            curr = curr.next
        }
        curr.next = new ListNode(val);
    }
}

 

leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/

댓글0