[LeetCode] Merge Two Sorted Lists (JS)

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into 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.

두 개의 정렬된 Linked list list1과 list2가 주언다.

두 리스트를 하나의 정렬된 list로 병합하고 연결된 리스트의 헤드를 반환하라

 

 

 

풀이 

 

let resultList = new ListNode();
let head = list;

 

list1과 list2를 병합하여 새롭게 만들 list를 선언해준다

 

while (list1 !== null && list2 !== null) {
	if (list1.val < list2.val) {
    	resultList.next = new ListNode(list1.val);
        list1 = list1.next;
    } else {
    	resultList.next = new ListNode(list2.val);
        list2 = list2.next;
    }
    
    resultList = resultList.next;
}

 

list1과 list2를 순회하며 list1과 list2의 값을 비교하여 더 작은 값을 resultList의 다음 값으로 연결 시켜준다. 이때, 더 작은 값으로 판단되어 resultList에 연결되는 리스트는 연결 후 next로 포인터를 이동시키고 resultList의 포인터 역시 다음 값으로 이동시켜 주어야 한다. 

 

if (list1 !== null) {
	resultList.next = list1;
}

if (list2 !== null) {
	resultList.next = list2;
}

 

한 리스트가 다른 리스트보다 짧은 경우도 있기 때문에 이경우에는 resultList에 값이있는 list값을 next로 연결한다. 

  return head.next;

LinkedList의 첫 값은 비어있기 때문에 head의 다음 값을 return 해 준다.

답안

var mergeTwoLists = function(list1, list2) {
    let resultList = new ListNode();
    let head = resultList;
    
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            resultList.next = new ListNode(list1.val);
            list1 = list1.next;
        } else {
            resultList.next = new ListNode(list2.val);
            list2 = list2.next;
        }
        resultList = resultList.next;
    }
    
    if (list1 !== null) {
        resultList.next = list1;
    }
    
    if (list2 !== null) {
        resultList.next = list2;
    }
    
    return head.next;
};

시간/공간 복잡도

시간 복잡도  : O(m+n)

위 알고리즘은 두 목록을 한 번씩 순회하기 때문에 노드 길이의 합에 비례하다. 따라서 m과 n은 각각 list1과 list2의 길이를 의미한다.

 

공간 복잡도 : O(1)

입력된 LinkedList의 크기에 관계없이 일정 양의 추가 공간을 사용하기 때문에 공간 복잡성은 O(1)이다.