Merge k Sorted Lists (opens in new tab)

leetcode.com Problem Statement Given K sorted linked lists, merge them into one sorted linked list. Brute Force Intuition Put all nodes into an array. Sort the array. Create a new linked list. Complexity Time Complexity: O(N log N) Space Complexity: O(N) Where: N = Total Nodes Better Heap Approach Push first node of every list into Min Heap. Repeatedly: Take smallest node Insert next node Complexity O(N log K) Moving Towards Optimal Instead of merging one list at a time: Merge Lists Pairwise ...