思路分析
- 因为两个链表都是有序的，所以这里就循环依次取出他们的首节点，判断大小，小的接到新链表上即可。
- 其中要注意循环结束的条件是两个链表都为空，代表循环完了，但是当其中一条链表遍历完之后，直接让新链表指向另一条链表即可，无需继续循环了。
- 再注意要确保两个链表都有值的状态下，才取出值进行对比，否则会报空指针错。
复杂度：时间复杂度: O ( n ) O(n) O(n) | O ( m + n ) O(m+n) O(m+n)、空间复杂度: O ( 1 ) O(1) O(1)
- 时间复杂度:
O
(
n
)
O(n)
O(n) |
O
(
m
+
n
)
O(m+n)
O(m+n)
mergeTwoLists 函数的时间复杂度为 O ( m + n ) O(m+n) O(m+n)。在最坏的情况下，需要遍历两个链表中的所有节点，指向合并操作。如果其中一个链表为空，时间复杂度为 O ( n ) O(n) O(n)或 O ( m ) O(m) O(m)，取决于非空链表的长度。
- 空间复杂度:
O
(
1
)
O(1)
O(1)
mergeTwoLists 函数的空间复杂度为 O ( 1 ) O(1) O(1)，因为仅使用了常量级别的额外空间来存储变量和指针，与输入链表的大小无关。不论两个链表的长度符合，额外的空间使用都保持不变，是 O ( 1 ) O(1) O(1)。
Go代码
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
newList := &ListNode{}
tmp := newList
tmp1 := list1
tmp2 := list2
for {
if tmp1 == nil && tmp2 == nil {
break
}
if tmp1 == nil {
tmp.Next = tmp2
break
}
if tmp2 == nil {
tmp.Next = tmp1
break
}
// 两个链表都有值时才能对比大小
if tmp1.Val >= tmp2.Val {
tmp.Next = tmp2
tmp2 = tmp2.Next
} else {
tmp.Next = tmp1
tmp1 = tmp1.Next
}
tmp = tmp.Next
}
return newList.Next
}
代码再优雅些
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
newList := &ListNode{}
tmp, tmp1, tmp2 := newList, list1, list2
for tmp1 != nil && tmp2 != nil {
// 两个链表都有值时才能对比大小
if tmp1.Val >= tmp2.Val {
tmp.Next = tmp2
tmp2 = tmp2.Next
} else {
tmp.Next = tmp1
tmp1 = tmp1.Next
}
tmp = tmp.Next
}
if tmp1 != nil {
tmp.Next = tmp1
}
if tmp2 != nil {
tmp.Next = tmp2
}
return newList.Next
}
思路分析
- 因为上面已经做过合并两个有序链表的函数了，这里只要将前两个合并，之后再将后面的逐步合并进来即可。
复杂度：时间复杂度: O ( k 2 ∗ n ) O(k^2*n) O(k2∗n)、空间复杂度: O ( 1 ) O(1) O(1)
- 时间复杂度:
O
(
k
2
∗
n
)
O(k^2*n)
O(k2∗n)
mergeKLists 函数使用了一个循环来逐个合并K个有序链表。假设每个链表的平均长度是n，那么第一次合并的时间复杂度是 O ( n ) O(n) O(n)（就是mergeTwoLists合并两个链表的时间复杂度），第二次 O ( 2 n ) O(2n) O(2n)，第三次 O ( 3 n ) O(3n) O(3n)，以此类推，最后一次是 O ( k n ) O(kn) O(kn)。因此，总的时间复杂度是 O ( n + 2 n + 3 n + . . . + k n ) O(n+2n+3n+...+kn) O(n+2n+3n+...+kn)。这个级数的求和结果是 O ( k 2 ∗ n ) O(k^2*n) O(k2∗n)。因此，mergeKLists 函数的时间复杂度是 O ( k 2 ∗ n ) O(k^2*n) O(k2∗n)。其中 k 是输入链表数组的长度，n是每个链表的平均长度。
- 空间复杂度:
O
(
1
)
O(1)
O(1)
mergeKLists 函数使用了一个额外的链表 newlist 来存储合并后的结果。在合并K个链表的过程中，始终只有一个新链表被使用，因此空间复杂度是 O ( 1 ) O(1) O(1)，是常量级别的额外空间。
Go代码
func mergeKLists(lists []*ListNode) *ListNode {
var newlist *ListNode
if len(lists) == 0 {
return newlist
}
if len(lists) == 1 {
return lists[0]
}
for _, list := range lists {
newlist = mergeTwoLists(newlist, list)
}
return newlist
}