LeetCode23 Merge k Sorted Lists 把K个有序链表连接成一个

题目：

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

翻译：

把K个有序的链表合成一个，返回。

思路：

这道题和昨天的Merge 2 Lists有些类似。但是k不确定，如果用每个都去遍历的话，肯定是不会通过的。

So、可以想到的是归并方法。

还记得大一刚开始组长布置的归并作业，那时候刚入门，看的云里雾里。

正好借此机会把归并好好的复习一下。

先说一下这道题的解法：

因为是链表List，可以通过分治，把他分解成2个一组，然后对每组的2个进行Merge 2Lists。

接着在4个一组，因为上一步已经形成了2个链，所以此时也可通过Merge 2Lists进行，递归即可得到结果。

代码：

public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0)return null; return MergeSort(lists, 0, lists.length-1); } public static ListNode MergeSort(ListNode[] lists,int l ,int r) { if(l>=r)return lists[l]; int m = (l+r)/2; ListNode ll = MergeSort(lists, l, m); ListNode rr = MergeSort(lists, m+1, r); return Merge(ll,rr);} public static ListNode Merge(ListNode l1,ListNode l2) { ListNode root =new ListNode(0); ListNode pre = root; pre.next = l1; while(true) {if(l1 == null){pre.next = l2;break;}if(l2 == null){pre.next = l1;break;}if(l1.val < l2.val){pre.next = l1;l1 = l1.next;}else{pre.next = l2;l2 = l2.next;}pre = pre.next;} return root.next;}好了，这道题的代码就是上面。

这里，还是要把归并写一写。因为毕竟以后要用到。

归并排序wiki解释

个人的理解就是把一个长的分解成小部分，即分治，分成2个一组，把每组排序后，在进行4个一组，，排序。

最后得到整体的有序排列。

百度一张图片，估计对理解有帮助

Wiki的解释：

归并排序具体工作原理如下（假设序列共有n个元素）：

于是乎，自己写一个归并排序吧。

public class MergeSort {static int number=0;public static void MergeSort(int arr[],int l , int r){if(l >= r)return ;int mid = (l+r)/2;MergeSort(arr, l, mid);//分成组MergeSort(arr, mid+1, r);Merge(arr, l, mid, r);//组内排序}public static void Merge(int arr[],int l,int mid, int r){int []tep = new int[arr.length];int mm = mid+1;int count = l,ll = l;while(l <= mid && mm <= r){if(arr[l] <= arr[mm])tep[count++] = arr[l++];elsetep[count++] = arr[mm++];}while(l<= mid){tep[count++] = arr[l++];}while(mm <=r){tep[count++] = arr[mm++];} System.out.println("第"+(++number)+"趟\t");while(ll<=r){ arr[ll] = tep[ll]; System.out.print(arr[ll] + "\t"); ll++;} System.out.println();}/** * @param args */public static void main(String[] args) {// TODO 自动生成的方法存根int[] a = {9,20,32,12,53,23,54,2}; MergeSort(a, 0, a.length-1);for(int t:a){System.out.println(t);}}}输出结果：

输出中可以清楚的看出分组后排序的效果。

话说提交后看到一群人用C写才十几毫秒就通过了。果然屌！

等会研究研究他们的写法。然后在修改。

真正的爱，应该超越生命的长度、心灵的宽度、灵魂的深度

相关文章：

你感兴趣的文章：

标签云：