[数据结构与算法]??合并K个升序链表??

问题描述

来源：LeetCode第23题
难度：困难

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

示例 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

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

归并排序

这题可以看到，结果是要把链表数组合并成最终的链表，典型的归并排序算法。请看我之前写的归并排序：什么是归并排序？

主要分为以下几个步骤：

1，合并两个链表

需要将两个有序的链表合并成一个有序链表，这是算法的核心，用递归可以实现。

//合并两个链表
public static ListNode mergeTwoNode(ListNode a,ListNode b){
    if(a==null) return b;
    if(b==null) return a;
    if(a.val<b.val){
        a.next=mergeTwoNode(a.next,b);
        return a;
    } else{
        b.next=mergeTwoNode(a,b.next);
        return b;
    }
}

2，拆分链表

给我们一个无序链表，现在需要做的就是将链表无限拆分，拆为两个有序的链表。

//拆分链表
public static ListNode merge(ListNode[] lists,int start,int end){
   if(start==end){
       return lists[start];
   }
    int mid=(start+end)/2;
    ListNode l1=merge(lists,start,mid);
    ListNode l2=merge(lists,mid+1,end);
    //合并拆分完成的有序链表
    return mergeTwoLists(l1,l2);
}

完整代码

经过上述两个步骤，我们就可以完成题目要求。

第一步：建立三个如题述的链表，形成一个链表数组；

第二步：调用上述拆分链表的方法；

第三步：输出链表，用while循环；

public static void main(String[] args) {
        //结点list1
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(4);
        ListNode node3=new ListNode(5);
        node1.next=node2;
        node2.next=node3;
        //结点list2
        ListNode node4=new ListNode(1);
        ListNode node5=new ListNode(3);
        ListNode node6=new ListNode(4);
        node4.next=node5;
        node5.next=node6;
        //结点list3
        ListNode node7=new ListNode(2);
        ListNode node8=new ListNode(6);
        node7.next=node8;
        //lists
        ListNode[] lists=new ListNode[3];
        lists[0]=node1;
        lists[1]=node4;
        lists[2]=node7;

        //调用方法
        ListNode newList=merge(lists,0,lists.length-1);
        //输出链表
        ListNode cur=newList;
        while(cur!=null){
            System.out.print((cur.val)+" ");
            cur=cur.next;
        }
    }