Merge k sorted lists

ゝ一纸荒年。 2022-10-01 00:39 22阅读 0赞

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

本题是合并两个已经排好序的lists的扩展版，所以基于之前写过的对两个排序链表的merge过程。考虑采用归并递归的方式，每一次我们对其中的两个链表进行整合，将所有底层链表整合之后再对已经整合好的链表进行整合，直到所有链表整合完毕，整个过程参考递归排序的方式。其中时间复杂度为O(nklog(k))。代码如下所示

public class MergeKSortedLists {
        public ListNode mergeKLists(ListNode[] lists) {
            //ListNode list = new ListNode(0);
            //ListNode listresult = list;
            if(lists==null || lists.length==0){
                return null;
            }
            return merge(lists,0,lists.length-1);
        }
        public ListNode merge(ListNode[] lists,int l,int r){
            if(l<r){
                int m = (l+r)/2;
                return mergeTwoLists(merge(lists,l,m),merge(lists,m+1,r));
            }
            return lists[l];
        }
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode result = new ListNode(0);
            ListNode result1 = result;
            result.next = l1;
            while(l1!=null && l2!=null){
                if(l1.val>l2.val){
                    ListNode next = l2.next;
                    l2.next = result1.next;
                    result1.next = l2;
                    l2 = next;
                }
                else{
                    l1 = l1.next;
                }
                result1 = result1.next;
            }
            if(l2!=null){
                result1.next = l2;
            }
            return result.next;
        }
    }