23.合并K个排序链表(题目解析+思路分析+代码行注释)

最近我把做过的题目 题解+思路+代码+代码注释 都放到了 github上,有需要的自取 github地址

题目:

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解析题目:

一个有序的链表数组,将里面的所有值按照顺序重新排列成一个有序链表

思路:

• 解法1: 暴力解题,反正题目没有要求,那么,我可以把所有的值全部拿出来放到一个数组里,然后将数组进行排序,排完之后,依次转换成一个链表
• 解法2: 依次合并链表,比如数组长度为4,那么把第一个和第二个有序合并,第三个和第四个有序合并,然后再把上面的两个再次进行合并!
• 解法3: 按照每个链表从头开始遍历,比如上面的示例里,先从三个链表的头开始遍历,挨个比较,分成三个指针,不同顺序进行前后遍历,界定条件是有其他值大于当前的这个指针,那么指针往下移动,直到 nil (此方法是一种思路,没写代码实现)
• 解法4: 先去做一下 合并两个有序链表
  • 依次遍历数组
  • 可以每两个进行合并,得到新的数组链表,再继续合并到最后一个链表为止
  • 也可以第一个和第二个合并,得新链表,然后新链表和第三个合并,一直合并到最后一个!
  • 我用后面这个方法解的,因为我刚刚做完合并两个有序链表,可以拿来直接用

代码:

发现第一种解法特别简单,然后几分钟就写出来了

var values []int
	listLen := len(lists)
	if listLen == 0 {
		return nil
	}
	for i:=0;i<listLen;i++ {
		ls := lists[i]
		for ls != nil  {
			values = append(values,ls.Val)
			ls = ls.Next
		}
	}
	sort.Sort(sort.IntSlice(values))

	newList := &ListNode{
	}
	head := newList
	for k,v := range values {
		head.Next = &ListNode{
			Val:v,
		}
		if k == len(values) {
			head.Next = nil
		}
		head = head.Next
	}

	return newList.Next

列一下解法四

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 1 {
		return lists[0]
	}

	var list *ListNode
	for i:=0;i<len(lists);i++ {
		if i == 0 {
			list = mergeTwoLists(lists[0],lists[1])
			i++
			continue
		}
		list = mergeTwoLists(list,lists[i])
	}

	return list
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {

	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}
	newNode := &ListNode{Val:0}
	head := newNode
	for l1 != nil && l2 != nil {
		if l1.Val > l2.Val {
			newNode.Next = l2
			l2 = l2.Next
		} else {
			newNode.Next = l1
			l1 = l1.Next
		}
		newNode = newNode.Next
	}

	if l1 != nil {
		newNode.Next = l1
	}

	if l2 != nil {
		newNode.Next = l2
	}

	return head.Next
}

---

欢迎转载,但请附上原文地址哦,尊重原创,谢谢大家 本文地址: https://www.iphpt.com/detail/135/

---

本站(PHP --> Golang)已重构,代码开源

• Golang版本 代码地址: https://github.com/izghua/go-blog
• 原PHP版本 代码地址: https://github.com/xzghua/laravel-5-myblog

---