[leetcode] merge K ascending linked lists

#LeetCode A daily topic 【 Special topic of linked list 】

• Merge K An ascending list
  https://leetcode-cn.com/problems/merge-k-sorted-lists/
• analysis
  Merge two ascending lists , It has been implemented many times before ; Now merge K An ascending list , Here's an array of linked lists , Merge into an orderly ;
  The easiest idea to think of is ： A cycle , Record the results in pairs
• Achieve one

//  Merge K An ordered list 
    //  loop 、 Split into merge 2 There is a sequence table 
    public ListNode mergeKLists(ListNode[] lists) {
    
        if (lists == null || lists.length == 0) {
    
            return null;
        }
        ListNode dummy = null, node = null;
        for (ListNode list : lists) {
    
            node = mergeTwoList(dummy, list);
            dummy = node;
        }
        return node;
    }

    private ListNode mergeTwoList(ListNode list1, ListNode list2) {
    
        ListNode result = new ListNode(0);
        ListNode temp = result;
        ListNode node1 = list1, node2 = list2;
        while (node1 != null && node2 != null) {
    
            if (node1.val < node2.val) {
    
                temp.next = node1;
                node1 = node1.next;
            } else {
    
                temp.next = node2;
                node2 = node2.next;
            }
            temp = temp.next;
        }
        if (node1 != null) {
    
            temp.next = node1;
        }
        if (node2 != null) {
    
            temp.next = node2;
        }
        return result.next;
    }

LeetCode Time consuming ：101ms

• Achieve two
  Divide and conquer ： Divide and rule , Constantly split in half , Final re merger ;
  This is also the idea of merging and sorting

//  Divide and conquer ： Divide and rule , Constantly split in half , Final re merger 
    //  This is also the idea of merging and sorting 
    public ListNode mergeKLists02(ListNode[] lists) {
    
        if (lists == null || lists.length == 0) {
    
            return null;
        }
        return mergeTwoList02(lists, 0, lists.length - 1);
    }

    //  recursive ： Don't fall into the trap of following him round by round ;
    //  Recursive Trilogy ：
    // 1.  What are the closing conditions 
    // 2.  What is the return value 
    // 3.  What does this level recursion need to do 

    /*  For example, every recursion ： 1、  The end condition ： Split to only one node , end ; Right here left=right, Marked the same position of the array  2、  What is the return value ： We need to handle the linked list  3、  What recursion at this level should do ： This level recursion , We have the split linked list on the left 、 The split linked list on the right , Then we can merge two linked lists  */
    private ListNode mergeTwoList02(ListNode[] lists, int left, int right) {
    
        if (left == right) {
    
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode nodeLeft = mergeTwoList02(lists, left, mid);
        ListNode nodeRight = mergeTwoList02(lists, mid + 1, right);
        return mergeTwoList(nodeLeft, nodeRight);
    }
    private ListNode mergeTwoList(ListNode list1, ListNode list2) {
    
        ListNode result = new ListNode(0);
        ListNode temp = result;
        ListNode node1 = list1, node2 = list2;
        while (node1 != null && node2 != null) {
    
            if (node1.val < node2.val) {
    
                temp.next = node1;
                node1 = node1.next;
            } else {
    
                temp.next = node2;
                node2 = node2.next;
            }
            temp = temp.next;
        }
        if (node1 != null) {
    
            temp.next = node1;
        }
        if (node2 != null) {
    
            temp.next = node2;
        }
        return result.next;
    }

LeetCode Time consuming ：1ms

fast 100 times ： Because use the result to merge the next , The linked list to be processed will be longer and longer ;
Divide and conquer method , Continuously split into two , A merger of two , Then go back and merge the two , Much less data than before

• summary
  Recursive routine ：https://lyl0724.github.io/2020/01/25/1/
  The recursion routine summarized in this article —— Trilogy , I feel very clear after reading
  1. What are the closing conditions
  2. What is the return value
  3. What does this level recursion need to do
     I hope you can directly answer similar questions later