题目解析

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并两数组，归并排序中的一个小步骤。 把这个小步骤演化为合并k个排好序的数组

分析步骤

1、我们先实现两排序数组或者链表合并， 此为基本编码思路
2、k个参数， 类比归并排序思想，两两合并
3、考察2中的递归逻辑以及递归退出条件

代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class A23MergeKSortedList {


    /**
     * 分治+递归
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists.length == 0) {// 边界值， 递归退出条件
            return null;
        } else if (lists.length == 1) {// 边界值， 递归退出条件
            return lists[0];
        } else if (lists.length == 2) {// 边界值， 递归退出条件
            return merge2Lists(lists[0], lists[1]);
        } else {
            ListNode[] params;
            if (lists.length % 2 == 0) { // 偶数个情况
                params = new ListNode[lists.length / 2];
                for (int k = 0; k < params.length; k++) {
                    params[k] = merge2Lists(lists[k], lists[lists.length - k - 1]);
                }
            } else { // 偶数个情况
                params = new ListNode[lists.length / 2 + 1];
                for (int k = 0; k < params.length - 1; k++) {
                    params[k] = merge2Lists(lists[k], lists[lists.length - k - 1]);
                }
                params[params.length - 1] = lists[lists.length / 2];
            }
            return mergeKLists(params); // 递归处理合并
        }

    }

    /**
     * merge2 合并两链表
     * @param list1
     * @param list2
     * @return
     */
    public ListNode merge2Lists(ListNode list1, ListNode list2) {
        ListNode node = new ListNode(0);
        ListNode head = node;
        while (true) {
            if (list1 == null) {
                node.next = list2;
                break;
            }
            if (list2 == null) {
                node.next = list1;
                break;
            }
            if (list1.val == list2.val) {
                node.next = new ListNode(list1.val);
                node.next.next = new ListNode(list1.val);
                node = node.next.next;
                list1 = list1.next;
                list2 = list2.next;
            } else if (list1.val < list2.val) {
                node.next = new ListNode(list1.val);
                list1 = list1.next;
                node = node.next;
            } else {
                node.next = new ListNode(list2.val);
                node = node.next;
                list2 = list2.next;
            }
        }
        return head.next;
    }

    public static void main(String[] args) {
        A23MergeKSortedList tmp = new A23MergeKSortedList();
        ListNode a = new ListNode(1);
        a.next = new ListNode(4);
        a.next.next = new ListNode(5);

        ListNode b = new ListNode(1);
        b.next = new ListNode(3);
        b.next.next = new ListNode(4);

        ListNode c = new ListNode(2);
        c.next = new ListNode(6);

        tmp.mergeKLists(new ListNode[]{a, b, c});
    }
}

代码文件：
A23MergeKSortedList.java
TODO： 实际解决方案，k个有序联表

总结

  • 就是和归并排序思想类似
  • 方案二，采用K大小的堆去维持合并的数据排序。待续

版权声明：本文为博主原创文章，未经允许不得转载。