本文共 3012 字，大约阅读时间需要 10 分钟。

题目描述

给定一个链表数组，数组中的每一个链表都是升序的，请你把数组中的所有链表按照升序的方式合并到一个链表中。

示例：

链表数组：【【0—>1】，【1—>2】，【2—>3】】

如果你有了前面的经验，那么本题暴力的方法就是遍历数组，统一看成两个链表合并的方式。

暴力解法

public class MergeMultipleLists {
       public static void main(String[] args) {
           MergeMultipleLists c = new MergeMultipleLists();        ListNode[] lists = new ListNode[3];        ListNode n1 = new ListNode(0);        ListNode n2 = new ListNode(1);        ListNode n3 = new ListNode(2);        lists[0] = n1;        lists[1] = n2;        lists[2] = n3;        System.out.println(c.mergeMultipleLists(lists));    }    public ListNode mergeMultipleLists(ListNode[] lists) {
           ListNode res = null;        for (int i = 0; i < lists.length; i++) {
               //合并两个链表            res = mergeTwoList(res, lists[i]);        }        return res;    }    private ListNode mergeTwoList(ListNode p1, ListNode p2) {
           if (p1 == null) {
               return p2;        }        if (p2 == null) {
               return p1;        }        ListNode mergeNode = new ListNode();        ListNode pre = mergeNode;        while (p1 != null && p2 != null) {
               if (p1.val < p2.val) {
                   pre.next = p1;                p1 = p1.next;            } else {
                   pre.next = p2;                p2 = p2.next;            }            pre = pre.next;        }        pre.next = p1 == null ? p2 : p1;        return mergeNode.next;    }}

归并的方式

暴力的方式显然不够优雅，回想一下，我们之前也遇到过了，实际上也适用于本题。

public class MergeMultipleLists {
       public static void main(String[] args) {
           MergeMultipleLists c = new MergeMultipleLists();        ListNode[] lists = new ListNode[0];        ListNode n1 = new ListNode(0);        ListNode n2 = new ListNode(1);        ListNode n3 = new ListNode(2);        lists[0] = n1;        lists[1] = n2;        lists[2] = n3;        System.out.println(c.mergeMultipleLists(lists));    }    public ListNode mergeMultipleLists(ListNode[] lists) {
           if(lists.length == 0){
               return null;        }        return process(lists, 0, lists.length - 1);    }    private ListNode process(ListNode[] lists, int l1, int l2) {
           if (l1 == l2) {
               return lists[l1];        }        int mid = l1 + ((l2 - l1) >> 1);        ListNode p1 = process(lists, l1, mid);        ListNode p2 = process(lists, mid + 1, l2);        return mergeTwoList(p1, p2);    }    private ListNode mergeTwoList(ListNode p1, ListNode p2) {
           if (p1 == null || p2 == null) {
               return p1 == null ? p2 : p1;        }        ListNode mergeNode = new ListNode();        ListNode pre = mergeNode;        while (p1 != null && p2 != null) {
               if (p1.val < p2.val) {
                   pre.next = p1;                p1 = p1.next;            } else {
                   pre.next = p2;                p2 = p2.next;            }            pre = pre.next;        }        pre.next = p1 == null ? p2 : p1;        return mergeNode.next;    }}

除了新增了process过程，合并过程不变。

转载地址：http://xhlrb.baihongyu.com/