[자료구조] Linked list : Leetcode - 21. Merge Two Sorted Lists

🤔 문제 이해

두개의 정렬된 링크드리스트를 하나의 정렬된 링크드리스트로 만들어라

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

 

🤔 EX

data example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

data example 2
Input: list1 = [], list2 = []
Output: []

data example 3
Input: list1 = [], list2 = [0]
Output: [0]

🤔 의사 코드

/**
 * 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 answer = new ListNode(0) 새로운 링크드리스트 선언
    let current = answer 현재 노드의 포인터
  
    while(list1 && list2){
         let list1Num = list1 ? list1.val : Infinity;
        let list2Num = list2 ? list2.val : Infinity;

        if(list1Num<list2Num){
			노드에 list1Num저장 후
             if(list1) list1 = list1.next 다음값으로 넘김
        }else if(list1Num == list2Num){
				노드에 list1Num저장 후
             if(list1) list1 = list1.next 다음값으로 넘김
			노드에 list2Num저장 후
             if(list2) list2 = list2.next 다음값으로 넘김
        }
        else{
            노드에 list1Num저장 후
            if(list2)  list2 = list2.next 다음값으로 넘김
            }
    }
     if (list1) {
          list1이 남은 경우, 나머지를 추가
    }

    if (list2) {
 		 list2가 남은 경우, 나머지를 추가
    }
    return answer.next
};

🤔 해결한 코드

var mergeTwoLists = function(list1, list2) {
    let answer = new ListNode(0)
    let current = answer
  
    while(list1 && list2){
         let list1Num = list1 ? list1.val : Infinity;
        let list2Num = list2 ? list2.val : Infinity;

        if(list1Num<list2Num){
            current.next = new ListNode(list1Num)
            current = current.next
           if(list1) list1 = list1.next

        }else if(list1Num == list2Num){

            current.next = new ListNode(list1Num)
            current = current.next
           if(list1) list1 = list1.next
           current.next = new ListNode(list2Num)
            current = current.next
           if(list2) list2 = list2.next

        }
        else{
            current.next = new ListNode(list2Num)
            current = current.next
            if(list2)  list2 = list2.next
            }
    }
     if (list1) {
        current.next = list1; // list1이 남은 경우, 나머지를 추가
    }

    if (list2) {
        current.next = list2; // list2가 남은 경우, 나머지를 추가
    }
    return answer.next
};

🤔 다른 풀이방법

var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2;
    else if (!l2) return l1;
    else if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2
    }
};

너무 간단하게 풀어내서 놀랐다....

코드 해석 

l1의 값이 l2의 값보다 작거나 같은 경우, l1의 다음 노드를 l1.next로 설정하고, l1.next와 l2를 재귀적으로 병합한 결과를 l1의 다음 노드로 설정합니다. 그리고 l1을 반환합니다. 이는 작은 값을 가진 노드를 기준으로 병합하는 것을 의미합니다.

l1의 값이 l2의 값보다 큰 경우, l2의 다음 노드를 l2.next로 설정하고, l1과 l2.next를 재귀적으로 병합한 결과를 l2의 다음 노드로 설정합니다. 그리고 l2를 반환합니다. 이는 작은 값을 가진 노드를 기준으로 병합하는 것을 의미합니다.