# __ .______ __ __ .______ .___________. ______ ______ .___ ___. # | | | _ \ | | | | | _ \ | | / | / __ \ | \/ | # | | | |_) | | |__| | | |_) | `---| |----` | ,----'| | | | | \ / | # | | | ___/ | __ | | ___/ | | | | | | | | | |\/| | # | | | | | | | | | | | | __ | `----.| `--' | | | | | # |__| | _| |__| |__| | _| |__| (__) \______| \______/ |__| |__| # ""$o o$"" ""$o o$" o "$""""o "o $" o""" $" "$o "$o" $o " $ o$" "$o $$$o$$$$o$$$$ $" "oooo o "" ""$$$$$$$$""o"" oo oooo" "$$$$$$oo"oo$$$o" o$$$$oo" o$$$o "o$$$$$$$ "$ $$$$$$$$$oo o$$$$$$$$$o"$" $ $$$ $$$$$$ o$$$$$$ "$$o"o $ $$$$o $$$$$$ $$$$$$$ $$$$o"o $ $$$$$ $$$$$" "$$$$$ $$$$$$ $ $o""""" """" """ """"""$" $ o$$$$$"""$$$$$"$$$$$""$$$$$ooo"o $ o"$o $$$$$$$$oo$$$$$$$$o $$"" $ oo$ "$$$$$$$$$$$$$$$$$$$$" o" o $oo o$$$"$ $$o"o $$$$$$$"" "$$$$$$$ o$$ $$$$o IPHPT BUG o$$$$" $ $$$$ o "$$$$$oo o$$$$$$ "o$$$$ $ $$$$$ o$$"" $ $$$$$o" "$$$$$$$$$$$$$ o o$$$$$o$ "" $$ $$" $ $$$" o"o$$$$$$$$$$$$ " "$$$ $ $$o o$$ "o $$ " $$$$$$$$$$$"o "$$ $ $$$ $$$ oo$ $ o""$$""$$$o " $"o$o $$$o o$$$$ o$$$"o"$oo$$$$o" o $o $$$$$oo$ $$$$o $$$$ $$$$ $$$$" $ $$$$$"" $$ o$$$ """$$$$"o" "$$$o "$$$o $$$" o """ $ $$$oo $$$$o" $$ o$$$"o" """"$ o$$$ o$" $$$ $ "$"" o$"o"$$o$$$$ "$$"o" o$$ "$oo $ " $$o $ "oo$"o$$$"o$o"$$$$o" o" $$$ ""$o $$ $$$o "o$$o$"$$"$$o$$o$$"$$o" $$$ ""o $$$ ""$$$ $$$$$$ $$$$ $" $$$$ $$ $$$$ $$$$"$$$o$ $"" $$$ $$$$ "$$$ """ $$$$ $$"" "$$ oo$" $ooo $ "$$ 23.合并K个排序链表(题目解析+思路分析+代码行注释)   -  叶落山城秋

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

题目:

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

示例:

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

解析题目:

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

思路:

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

代码:

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

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


欢迎转载,但请附上原文地址哦,尊重原创,谢谢大家 本文地址: https://www.iphpt.com/detail/135/
本站(PHP --> Golang)已重构,代码开源

当你能力不能满足你的野心的时候,你就该沉下心来学习