LeetCode 笔记--分治法

23. 合并K个升序链表

难度困难1216

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：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

解答

合并两个链表的方法很简单 数据结构的课上都讲过 对于这个题 首先想到的就是 写一个方法 来合并两个链表 然后把数组里面的链表一个个合并 但是这样做效率不高 分治法来合并 更优

也就是再写一个方法 把链表数组每次都再分一半 分了一半再递归 直到只剩一个 然后返回

public ListNode mergeKLists(ListNode[] lists) {
        return mergeTwoLists(lists,0,lists.length-1);
    }
    public ListNode mergeTwoLists(ListNode[] lists,int left,int right)
    {
        if (left>right)return null;
        if (left==right)return lists[left];
       ListNode leftLists=mergeTwoLists(lists,left,(left+right)/2);
        ListNode rightLists=mergeTwoLists(lists,(left+right)/2+1,right);
        return mergeTwoList(leftLists,rightLists);
    }
    ListNode mergeTwoList(ListNode l1,ListNode l2)
    {
        if (l1==null)return l2;
        if (l2==null )return l1;
        ListNode p1=l1;
        ListNode p2=l2;
        ListNode head=null  ;
        if (p1.val<=p2.val)
        {
            head=p1;
            p1=p1.next;
        }
        else
        {
            head=p2;
            p2=p2.next;
        }
        ListNode p3=head;
        while (p1!=null&&p2!=null)
        {
            if (p1.val<=p2.val)
            {
                p3.next=p1;
                p1=p1.next;
            }
            else
            {
                p3.next=p2;
                p2=p2.next;
            }
            p3=p3.next;
        }
        while (p1!=null)
        {
            p3.next=p1;
            p1=p1.next;
            p3=p3.next;
        }
        while (p2!=null)
        {
            p3.next=p2;
            p2=p2.next;
            p3=p3.next;
        }
        return head;
    }