leetcode0023 - Merge k Sorted Lists / Hard / Typescript

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

Merge k Sorted Lists - LeetCode

Time Complexity O(N log(N))

• N은 node의 총 개수
  • 모든 value 들을 array에 담는 데 O(N)
  • value들을 정렬할 때, O(N log(N))
  • linked list를 다시 만들 때, O(N)의 시간

Space Complexity O(N)

• value들을 정렬하기 위해서 만든 array가 O(N)
• linked list를 만드는 데 사용되는 공간이 O(N)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const ansValues = [];

    for(let i = 0; i < lists.length; i++) {
        let node = lists[i];
        while(node) {
            ansValues.push(node.val);
            node = node.next;
        }
    }
    ansValues.sort((a,b) => a-b);

    const ansNodes = new ListNode(0);
    let tail = ansNodes;

    for(let j = 0; j < ansValues.length; j++) {
        tail.next = new ListNode(ansValues[j]);
        tail = tail.next;
    }

    return ansNodes.next;
};