美文网首页
23、Merge k Sorted Lists

23、Merge k Sorted Lists

作者: liuzhifeng | 来源:发表于2017-10-24 19:32 被阅读0次

    题设

    Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
    
    Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
    
    public ListNode mergeKLists(ListNode[] lists){
    

    要点

    • 链表合并
    • 迭代
    • 归并排序

    对已经有序的k个链表进行合并,有两种思路:

    1、对lists中的每2个链表进行merge(merge可以直接采用归并排序的merge方法),形成新的链表;重复此操作,直到链表数组中的元素只有一个。这种迭代的方法最后跑出来的时间较长;

    
        public ListNode mergeKLists(ListNode[] lists){
            /*
               1、迭代的方法
             */
    
            /*
            int len = lists.length;
            if(len == 0 || lists == null)
                return null;
            if(len == 1)
                return lists[0];
            System.out.println("len: " + len);
            ListNode[] newList;
            while(len > 1){
                if(len % 2 != 0)
                    newList = new ListNode[len / 2 + 1];
                else
                    newList = new ListNode[len / 2];
                for(int i = 0;i < newList.length;i++){
                    if(i * 2 + 1 < len)
                        newList[i] = mergeForList(lists[i * 2] , lists[i * 2 + 1]);
                    else
                        newList[i] = lists[i * 2];
                }
    
                lists = newList;
                System.out.println(lists.length + "kkk");
                if(len % 2 == 0)
                    len /= 2;
                else
                    len = len / 2 + 1;
            }
            return lists[0];
        }
    

    2、递归的方法。其实仔细观察可得,对数组中每两个链表进行归并,生成新链表并重复的过程,类似归并排序中递归分解的过程。我们要做的是把一个链表数组递归分解直到每一个链表元素,然后进行merge即可,这其实就是对一系列的有序链表做归并排序(传统的归并排序中,数组内的元素为int,而这里改成了有序链表而已)

        public ListNode mergeKLists(ListNode[] lists){
            /*
                2、递归的方法
    
                其实仔细观察可得,对数组中每两个链表进行归并,生成新链表并重复的过程,类似归并排序中递归分解的过程
                我们要做的是把一个链表数组递归分解直到每一个链表元素,然后进行merge即可
             */
    
            int len = lists.length;
            if(len == 0 || lists == null)
                return null;
            if(len == 1)
                return lists[0];
            return mergeSortForKList(lists , 0 , len - 1);
        }
    
        /*
            k个有序链表的递归分解
            @list:  待合并的有序链表集合
            @low :  此次分解的低位
            @high:  此次分解的高位
    
            与归并算法思路相同,先对链表数组进行分解,直到区间内只剩下一个元素,进行merge
         */
        public ListNode mergeSortForKList(ListNode[] list , int low , int high){
            if(low == high)
                return list[low];
    
            if(low < high){
                int middle = (low + high) >> 1;
                ListNode left = mergeSortForKList(list, low, middle);
                ListNode right = mergeSortForKList(list, middle + 1, high);
    
                return mergeForList(left, right);
            }
    
            return null;
        }
    
        /*
            有序链表的归并算法
            @leftHead: 拆分后左链表头指针;
            @rightHead:拆分后右链表头指针;
    
            初始两个链表指针leftHead和rightHead都在头部。比较其对应的val值,将值小的接入新的链表,同时移动链表指针
            一个有序链表遍历完成后,需要将另一个链表剩下的元素接入新的链表
        */
        public ListNode mergeForList(ListNode leftHead  , ListNode rightHead){
    
            // 存储归并后新的有序链表,最后返回newHead.next
            ListNode newHead = new ListNode(-1);
            ListNode tempHead = newHead;
    
            // 比较val大小,移动链表并更新保存结果的有序链表
            while(leftHead != null && rightHead != null){
                if(leftHead.val < rightHead.val){
                    tempHead.next = new ListNode(leftHead.val);
                    leftHead = leftHead.next;
                    tempHead = tempHead.next;
                }
                else{
                    tempHead.next = new ListNode(rightHead.val);
                    rightHead = rightHead.next;
                    tempHead = tempHead.next;
                }
            }
    
            // 将未遍历完的链表接入
            if(leftHead == null)
                tempHead.next = rightHead;
            else
                tempHead.next = leftHead;
    
            // 返回归并后的有序链表
            return newHead.next;
    
        }
    

    相关文章

      网友评论

          本文标题:23、Merge k Sorted Lists

          本文链接:https://www.haomeiwen.com/subject/ujvxpxtx.html