链表类算法

链表类算法

分治法

1. 合并k个升序链表

   问题描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

   示例：

   输入：lists = [[1,4,5],[1,3,4],[2,6]]
   输出：[1,1,2,3,4,4,5,6]
   解释：链表数组如下：
   [
     1->4->5,
     1->3->4,
     2->6
   ]
   将它们合并到一个有序链表中得到。
   1->1->2->3->4->4->5->6

   思路：

   首先，两个升序链表的合并算法是最基本的算法，这个已经知道了。那么k个升序链表如何进行合并呢？如果是一个个的遍历，显然不是一个很好的方法。所以可以考虑分治法，让链表数组里的链表分成两组，每组分别进行合并，最后将两组合并在一起，这也是一个递归的过程。

   

   代码如下：

   class Solution {
       public ListNode mergeKLists(ListNode[] lists) {
           return merge(lists, 0, lists.length-1);
       }
   
       public ListNode merge(ListNode[] lists, int l, int r){
           if (l==r){
               return lists[l];
           }
   
           if (l > r){
               return null;
           }
   
           int mid = (l + r) >> 1;
           return mergeTwoLists(merge(lists, l, mid), merge(lists, mid+1, r));
       }
   
       public ListNode mergeTwoLists(ListNode a, ListNode b){
           if (a==null || b==null){
               return a==null?b:a;
           }
   
           ListNode head = new ListNode(0);
           ListNode tail = head, aPtr = a, bPtr = b;
           while(aPtr!=null && bPtr!=null){
               if (aPtr.val < bPtr.val){
                   tail.next = aPtr;
                   aPtr = aPtr.next;
               }else{
                   tail.next = bPtr;
                   bPtr = bPtr.next;
               }
   
               tail = tail.next;
           }
   
           tail.next = aPtr==null?bPtr:aPtr;
   
           return head.next;
       }
   }