leetcode23 合并K个排序链表

分手后的思念是犯贱 2023-06-19 06:49 19阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:  
\[  
1->4->5,  
1->3->4,  
2->6  
\]  
输出: 1->1->2->3->4->4->5->6

思路：把初始的每一个链表当成数组中的一个数，做数组的归并排序。

递归的merge过程就是稍微慢一点，因为来回跳函数栈，所以你们看到只击败了90.

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length == 0) return null;
            return solve(lists, 0, lists.length-1);
        }
        
        private ListNode solve(ListNode[] arr, int left, int right){
            if(left == right) return arr[left];
    
            int mid = (left + right) >> 1; 
            ListNode lNode = solve(arr, left, mid);   
            ListNode rNode = solve(arr, mid+1, right); 
    
            return merge(lNode, rNode);
        }
        
        private ListNode merge(ListNode node1, ListNode node2){
            if(node1 == null) return node2;
            if(node2 == null) return node1;
            
            if(node1.val < node2.val){
                node1.next = merge(node1.next, node2);
                return node1;
            }else{
                node2.next = merge(node1, node2.next);
                return node2;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019120420324176.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70