力扣T21: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

这个算法的逻辑类似于「拉拉链」，l1, l2类似于拉链两侧的锯齿，指针p就好像拉链的拉索，将两个有序链表合并。

代码中还用到一个链表的算法题中是很常见的「虚拟头节点」技巧，也就是dummy节点。你可以试试，如果不使用dummy虚拟节点，代码会复杂一些，而有了dummy节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	p1, p2 := list1, list2
	var head, curNode *ListNode
	if p1 == nil{
		return p2
	}
	if p2 == nil{
		return p1
	}
	if p1.Val > p2.Val{
		head, curNode = p2, p2
		p2 = p2.Next
	}else{
		head,curNode = p1, p1
		p1 = p1.Next
	}
	for p1 != nil && p2 != nil{
		if p1.Val > p2.Val{
			curNode.Next = p2
			p2 = p2.Next
		}else{
			curNode.Next = p1
			p1 = p1.Next
		}
		curNode = curNode.Next
	}
	if p1 == nil{
		curNode.Next = p2
	}else{
		curNode.Next = p1
	}
	return head
}

 

递归法

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil{
		return list2
	}
	if list2 == nil{
		return list1
	}
	
	var head *ListNode
	if list1.Val < list2.Val{
		head = list1
		list1.Next = mergeTwoLists(list1.Next, list2)
	}else{
		head = list2
		list2.Next = mergeTwoLists(list2.Next, list1)
	}

	return head
}

 

力扣T23：合并k个有序链表

这道题我们还是可以用上一题的做法来做，假如有a~d这4条单链表（k=4），可以先合并a和b得到ab，再合并ab和c得到abc，以此类推。假设总结点数为N。

这样做的话，我们需要k个指针，用一个while循环同时遍历k个链表，每次遍历都要做k次比较，每次遍历经过k次比较后只能遍历某条链表的1个节点，因此我们需要做N次遍历。所以时间复杂度为kN，空间复杂度为N。

 

优化的思路是如何快速得到k个节点中最小的节点。可以使用优先队列（二叉堆）。将k个节点放入优先队列中，之后每从头部弹出一个就再从尾部放入一个，让优先队列的大小始终保持k个节点。每次放入一个节点会发生上浮操作，复杂度为logk；每次弹出节点会把尾部节点放到头部节点的位置再对头部节点进行下沉操作，复杂度为logk。一共要弹出和放入N次，总体时间复杂度为Nlogk，空间复杂度为N（优先队列占N个节点，合并后的结果链表占N个节点）。

旧方法的每次从k个节点得到最小的那个节点的复杂度为k，而优化的方法每次从k个节点得到最小的那个节点（即弹出和放入的操作）的复杂度为logk。

type nodeArr []*ListNode
func (this nodeArr) Len() int{return len(this)}
func (this nodeArr) Swap(a, b int) {this[a], this[b] = this[b], this[a]}
func (this nodeArr) Less(a, b int) bool{return this[b].Val > this[a].Val}
func (this *nodeArr) Push(x interface{}) {
	*this = append(*this, x.(*ListNode))
}
func (this *nodeArr) Pop() interface{}{
	lastNode := (*this)[len(*this)-1]
	*this = (*this)[:len(*this)-1]
	return lastNode
}

func mergeKLists(lists []*ListNode) *ListNode {
	arr := new(nodeArr)

	for _, list := range(lists){
		if list != nil{
			heap.Push(arr, list)
		}
	}

	dummy := &ListNode{}
	curNode := dummy
	for arr.Len() > 0{
		curNode.Next = heap.Pop(arr).(*ListNode)
		curNode = curNode.Next
		if curNode.Next != nil{
			heap.Push(arr, curNode.Next)
		}
	}
	return dummy.Next
}

 

除了使用优先队列，还可以使用分治法，该方法运用了递归，画出递归树可以看出其时间复杂度比约为N，空间复杂度约为Nlogk(也可以使用递归树看出)。

/* 法2：分治法 将k个链表分为两堆分别合并*/
func MergeKLists2(lists []*ListNode) *ListNode{
	length := len(lists)
	if length == 0{
		return nil
	}

	if length == 1{
		return lists[0]		// 如果k=1，即只有1个链表，就直接返回这个链表
	}

	// 分治法（其实是个树的后序遍历）
	num := length / 2
	left :=	MergeKLists(lists[:num])
	right := MergeKLists(lists[num:])
	return MergeTwoLists(left, right)
}

func MergeTwoLists(l1, l2 *ListNode) *ListNode{
	if l1 == nil{
		return l2
	}

	if l2 == nil{
		return l1
	}

	if l1.Val < l2.Val{
		l1.Next = MergeTwoLists(l1.Next, l2)
		return l1
	}
	l2.Next = MergeTwoLists(l1, l2.Next)
	return l2
}