//递归解法比较直接好想,不过递归会使用栈空间O(logk)
package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param lists ListNode类一维数组 * @return ListNode类 */ //合并两个有序列表O(n) func merge(a, b *ListNode ) *ListNode { var L ListNode var p *ListNode = &L for a != nil && b != nil { if a.Val <= b.Val { p.Next = a p = a; a = a.Next p.Next = nil }else { p.Next = b; p = b; b = b.Next; p.Next = nil; } } if a != nil { p.Next = a; }else { p.Next = b; } return L.Next; } //递归,利用归并排序思想 func M(lists []*ListNode, L, R int) *ListNode { if L > R { return nil; } if L == R { return lists[L]; } mid := (L+R)/2; L1 := M(lists, L, mid); L2 := M(lists, mid+1, R); return merge(L1, L2); } func mergeKLists( lists []*ListNode ) *ListNode { return M(lists, 0, len(lists)-1) }