[LeetCode] 23. Merge k Sorted Lists

https://leetcode.com/

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
   1->4->5, 1->3->4, 2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

 

Example 2:

Input: lists = []
Output: []

 

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 10^4.

 

Solutions Code 1 :

// 두 개의 정렬된 연결 리스트를 병합하는 함수
var mergeTwoLists = function(l1, l2) {
    // l1이 존재하지 않으면 l2를 반환
    if (!l1) {
        return l2;
    }
    // l2가 존재하지 않으면 l1을 반환
    if (!l2) {
        return l1;
    }
    // l1의 값이 l2의 값보다 작으면 l1의 다음 값을 l2와 병합하고 l1을 반환
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else { // l2의 값이 l1의 값보다 작거나 같으면 l2의 다음 값을 l1과 병합하고 l2를 반환
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};
// 여러 개의 정렬된 연결 리스트를 병합하는 함수
var mergeKLists = function(lists) {
    // 결과를 저장할 변수 초기화
    let ans = null;
    
    // 주어진 모든 리스트에 대해 반복하여 병합
    for (let i = 0; i < lists.length; i++) {
        // 현재 결과 리스트와 다음 리스트를 병합하여 결과를 갱신
        ans = mergeTwoLists(ans, lists[i]);
    }
    
    // 최종 병합된 리스트 반환
    return ans;
};

 

Solutions Code 2 :

var mergeKLists = function(lists) {
  // 우선순위 큐 생성
  const queue = new MinPriorityQueue({ priority: x => x.val })
  // 리스트의 헤드를 우선순위 큐에 추가
  for (const head of lists) {
    if (head) {
      queue.enqueue(head)
    }
  }
  // 결과를 저장할 빈 노드 생성
  let result = new ListNode()
  const head = result
  // 큐가 비어있지 않은 동안 연산을 반복
  while (!queue.isEmpty()) {
    // 큐에서 우선순위가 가장 높은 노드 추출
    const { val, next } = queue.dequeue().element
    // 추출한 노드의 값을 결과 노드에 추가
    result.next = new ListNode(val)
    result = result.next
    // 추출한 노드의 다음 노드가 존재하면 큐에 추가
    if (next) {
      queue.enqueue(next)
    }
  }
  // 결과 노드의 다음 노드 반환
  return head.next
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode