Leetcode discuss: 23. Merge k Sorted Lists

Here is the post.

C# merge two lists idea practice in August 2015

June 11, 2020

It is so challenge to learn something from algorithm called merge k sorted lists. I wrote C# solution based on the blog written in Chinese in August 2015.

Problem statement:
Merge k sorted lists and return one sorted list.
Assuming that all lists are sorted in ascending order.

Case study:
Merge 5 sorted linked lists in ascending order
List 1: 1->3->5->7
List 2: 2->4->6->8
List 3: 3->5->7->9
List 4: 4->6->8->10
List 5: 5->7->9->11

The idea proposed here is to merge two linked list together, List 1 and List 3 are merged first denoted as L13, List 2 and List 4 are merged next denoted as L24.

Next there are three linked lists to merge
List 13: 1->2->3->4->5->6->7->8
List 24: 3->4->5->6->7->8->9
List 5: 5->7->9->11

The idea is simple, and it is a good practice to write a while loop to merge two linked list.

Time complexity:
Will be added later.

I like to review the code and then learn my own experience.

A few things I like to tell from my practice back in 2015 through the following code:

1. Merge two lists, using the formula T(k) = 2T(k/2) + O(nk); detail check master theorem;
2. Two linked list can be written in iterative loop;
3. Warmup in June 2020, write a recursive function to merge two linked list.
4. Look into more about master theorem, and analyze time complexity.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MargeKSortedLists_2
{
    public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int v)
        {
            val = v;
        }
    }

    class MargeKSortedLists_B_No23
    {
        static void Main(string[] args)
        {
            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(4);
            l1.next.next = new ListNode(7);

            ListNode l2 = new ListNode(2);
            l2.next = new ListNode(5);
            l2.next.next = new ListNode(8);

            ListNode l3 = new ListNode(3);
            l3.next = new ListNode(6);

            ListNode l4 = new ListNode(4);
            l4.next = new ListNode(9); 

           /* ListNode[] lists = new ListNode[3] { l1, l2, l3 };
            ListNode test = mergeKLists(lists);
            * */

            ListNode[] lists2 = new ListNode[4] { l1, l2, l3, l4 };
            ListNode test2 = mergeKLists(lists2); 

        }

        /*
         * from blog: 
         * http://www.cnblogs.com/TenosDoIt/p/3673188.html
         * 
         * 算法2：利用分治的思想把合并k个链表分成两个合并k/2个链表的任务，一直划分，
         * 知道任务中只剩一个链表或者两个链表。可以很简单的用递归来实现。
         * 因此算法复杂度为T(k) = 2T(k/2) + O(nk),很简单可以推导得到算法复杂度为O（nklogk）

           递归的代码就不贴了。下面是非递归的代码非递归的思想是（以四个链表为例）：                   
         * 本文地址

            1、3合并，合并结果放到1的位置

            2、4合并，合并结果放到2的位置

            再把1、2合并（相当于原来的13 和 24合并）
         * 
         * Julia's comment: 
         * 1. pass online judge
         * 130 / 130 test cases passed.
            Status: Accepted
            Runtime: 204 ms
         */

        public static ListNode mergeKLists(ListNode[] lists) {
            int n = lists.Length;

            if(n == 0)
                return null;

            while(n >1)
            {
                int k = (n+1)/2;
                for(int i = 0; i < n/2; i++)
                    lists[i] = merge2list(lists[i], lists[i + k]);
                n = k;
            }

            return lists[0];
        }
    
        private static ListNode merge2list(ListNode head1, ListNode head2)
        {
            ListNode node = new ListNode(0), 
                res = node;

            while(head1 != null  && head2 != null)
            {
                if(head1.val <= head2.val)
                {
                    res.next = head1;
                    head1 = head1.next;
                }
                else
                {
                    res.next = head2;
                    head2 = head2.next;
                }

                res = res.next;
            }
            if(head1 != null)
                res.next = head1;
            else if(head2 != null)
                res.next = head2;

            return node.next;
        }
    }
}