合并k个有序链表
主要思想是分治和递归，首先用二分法将k个链表不断二分，直到细分到两个链表，然后将这两个有序链表合并，然后继续重复合并的过程，直到所有链表合并完成。可以理解成不停的拆分，拆分至合并两个有序链表的子问题。然后组装若干个子问题，直到所有子问题解决就得到原问题的解。
/* * 合并k个有序链表 */ public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; return merge(lists, 0, lists.length-1); } private ListNode merge(ListNode[] lists, int left, int right) { if(left==right) return lists[left]; int mid = left+(right-left)/2; ListNode l1 = merge(lists, left, mid); ListNode l2 = merge(lists, mid+1, right); return mergeTwoLists(l1, l2); } /* * 合并两个有序链表(递归) */ public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; if(l1.val<=l2.val){ l1.next = mergeTwoLists(l1.next,l2); return l1; }else{ l2.next = mergeTwoLists(l1,l2.next); return l2; } }
合并两个有序链表有两种方式，递归和非递归，上面是递归的代码，下面是非递归的代码
/* * 合并两个有序链表（迭代） */ public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while(l1!=null && l2!=null){ if(l1.val<=l2.val){ prev.next = l1; l1 = l1.next; }else{ prev.next = l2; l2 = l2.next; prev = prev.next; } } prev.next = l1==null?l2:l1; return prehead.next; }
原文：https://www.cnblogs.com/chenbo820/p/11660377.html
