Jamzen的技术博客
0%

LeetCode.合并k个升序链表

发表于 分类于 Valine：

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

  • 示例 1：
    输入：lists = [1->4->5,1->3->4,2->6]
    输出：[1->1->2->3->4->4->5->6]

解法：

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
object MergeKSortedLinkedList {

     def main(args: Array[String]): Unit = {

          println(
               solution1(
                    Array(
                         ListNode(1, ListNode(4, ListNode(5, null))),
                         ListNode(1, ListNode(3, ListNode(4, null))),
                         ListNode(2, ListNode(6, null))
                    )
               )
          )

          println(
               solution1(
                    Array(
                         ListNode(1, ListNode(4, ListNode(5, null))),
                         ListNode(1, ListNode(3, ListNode(4, null)))
                    )
               )
          )

          println(
               solution1(
                    Array(
                         ListNode(1, ListNode(4, ListNode(5, null)))
                    )
               )
          )

          println(solution1(Array()))

          println(
               solution3(
                    Array(
                         ListNode(1, ListNode(4, ListNode(5, null))),
                         ListNode(1, ListNode(3, ListNode(4, null))),
                         ListNode(2, ListNode(6, null))
                    )
               )
          )

     }

     /**
      * O(k*k*n)
      */
     def solution1(nodes: Array[ListNode]): ListNode = {

          val heads = new Array[ListNode](nodes.length)

          if (nodes.length == 1) {
               return nodes(0)
          }

          for (i <- 0 until nodes.length) {
               heads(i) = nodes(i)
          }

          val res = ListNode(-1, null)
          var cur = res

          while (!heads.isEmpty && heads.filter(_ != null).length != 0) {
               var min = Int.MaxValue
               var minHead = -1
               for (i <- 0 until heads.length) {
                    if (heads(i) != null && heads(i).x < min) {
                         min = heads(i).x
                         minHead = i
                    }
               }

               cur.next = heads(minHead)
               heads(minHead) = heads(minHead).next
               cur = cur.next
          }

          res.next
     }

     /**
      * 可以分治，把外层降为logk, 因此O(logk*k*n),实现暂无
      */
     def solution2(nodes: Array[ListNode]): ListNode = {
          null
     }

     /**
      * 在方法1基础上求最小可以使用优先队列，可以把内层k降为logk,因此O(k*logk*n)
      */
     def solution3(nodes: Array[ListNode]): ListNode = {

          val queue = new java.util.PriorityQueue[ListNode]((o1: ListNode, o2: ListNode) => {o1.x - o2.x})

          if (nodes.length == 1) {
               return nodes(0)
          }

          val res = ListNode(-1, null)
          var cur = res

          for(head <- nodes){
               queue.offer(head)
          }

          while (!queue.isEmpty) {
               val node = queue.poll()
               cur.next = node

               if (node.next != null) {
                    queue.offer(node.next)
               }
               cur = cur.next
          }

          res.next
     }

     case class ListNode(x: Int, var next: ListNode)

}