Leetcode 23: Merge K Sorted Lists

July 30, 2018

Introduction

It is hard level algorithm and I like to review the algorithm. I like to review the topic and get the idea what to work on next. Here is the blog.

Based on one in 2015

What I did is like a teacher to help a student, and review her home work after more than two years. Since my last practice is two years 11 months ago, it was August 2015.

1. One sample test case is added from line 26 to line 50.
2. The code is reviewed and make it more readable.
   The merge of two lists is in place. The result will be saved in one of lists. So no extra space is needed.
3. The desgin of function MergeKLists is added in the comment. The main idea to apply master theorem to beat the time complexity of naive approach O(n * k * k), the optimal time complexity is O(n * k * logk).
4. Line 91 variable name is called dummyNode to remind me to go to next one to return at the end of function.
5. add two pointer technique, and write comment to help understand two pointer technique to merge two linked list.
6. edge case handling - it is to append to unfinished linked list to the first list. No need to create a new node and copy the value.


Here is C# practice in 2018 with optimal time complexity.
Here is C# practice in 2015 with optimal time complexity.
Here is the brute force solution - O(n * K * K) - not optimal time complexity, written in 2015

Here is the blog I wrote in 2016 for the practice of Leetcode 23: merg k sorted lists.