进入了7月12号了，本来预计计划的7月份开始的第一周学习，结果到现在，整整推迟了12天的时间。还是得一直严于律己，稍微一放松，就会落后很多啊！
今天做了三道链表相关的题目：
- 合并两个有序l链表
- 合并k个有序链表
- 反转链表
- 链表中删去和为0的连续节点
合并两个有序l链表
这个是在之前面试中出现的题目，当时直接gg了，别面试官看出了很多问题，之前做过的题目，为什么做了一遍，就啥都没有了呢？忘记了？这确实是导致问题产生，当时盲目的一个原因，那这个原因怎么解决呢？我想了下，就做了今天这件事，总结！总结这件事，给我带来了很直观的两个好处：一是，加深对题目的印象和理解，要是还能有人和你讨论讨论，那就效果加倍了；二是，及时反馈，给自己的长期计划带来实时的动力。
看题目吧
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var head ListNode // 问题1
var tmp = &head
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
tmp.Next = l2 // 问题2
l2 = l2.Next
} else {
tmp.Next = l1
l1 = l1.Next
}
tmp = tmp.Next
}
if l1 != nil {
tmp.Next = l1
}
if l2 != nil {
tmp.Next = l2
}
return head.Next
}
看着码有点多啊！别怕，关键点，或者是我再书写过程中有疑惑的点：
- 问题1，如何返回头结点：看下上面代码的注释，就是这个，就是这两个变量的声明，我发现使用了这个声明之后，明显在后续逻辑可以毫无顾忌的写了。
- 问题2，后续节点的赋值：看下吧，后续节点的赋值可以使用这种方式，是不是如丝般顺滑
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var head ListNode
var tmp = head.Next
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
tmp = l2
l2 = l2.Next
} else {
tmp = l1
l1 = l1.Next
}
tmp = tmp.Next
}
if l1 != nil {
tmp = l1
}
if l2 != nil {
tmp = l2
}
return head.Next
}
当然，你也会使用这中反方式，看着是没啥区别，但是完全断开的链表的关系。串联链表必须使用Next进行。
合并k个有序链表
做了第一题后，再进行这题就思路清晰了很多。当然，做这题后我也有新的收获啊：
原来我这怎么写的：
func mergeKLists(lists []*ListNode) *ListNode {
var head ListNode
var tmp = &head
var num = 0
for num != len(lists) {
num = 0
var val = math.MaxInt32
var n = 0
for k, v := range lists {
if v == nil {
num++
continue
}
if v.Val <= val {
n = k
val = v.Val
}
}
if num == len(lists) {
break
}
tmp.Next = lists[n]
lists[n] = lists[n].Next
tmp = tmp.Next
}
return head.Next
}
可以吧，我先说下思路，就是遍历每个链表，找到最小的，然后进行合并。这个是O(n*N)的，今天有突然想到了这种解法，每个都是有序的，两两合并不也可以吗？两两合并，不就是合并两个有序链表吗？对的
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0{
return nil
}
if len(lists) < 2 {
return lists[0]
}
var head ListNode
var tmp = &head
var tmpList = lists[0]
for i := 1; i < len(lists); i++ {
tmpList = mergeTowList(tmpList, lists[i])
}
tmp.Next = tmpList
return head.Next
}
func mergeTowList(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var head ListNode
var tmp = &head
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
tmp.Next = l2
l2 = l2.Next
} else {
tmp.Next = l1
l1 = l1.Next
}
tmp = tmp.Next
}
if l1 != nil {
tmp.Next = l1
}
if l2 != nil {
tmp.Next = l2
}
return head.Next
}
反转链表
我只想说，我也没想到，这么简单，这里我默写一个
func reverseList(list *ListNode) *ListNode {
var pre *ListNode
var mid = list
for mid != nil {
var t = mid.Next
mid.Next = pre
pre = mid
mid = t
}
return pre
}
链表中删去和为0的连续节点
这中间也出现了挺多的问题
问题1：如何判断连续和为0：
这个问题的解法很多，我选择了On的前缀+哈希，暂且这么叫吧，大致的意思就是连续求和，并且把每一项和哈希统计，当出现重复的哈希时，就出现了和为0。很简单吧！我想的时候倒是想了很久
问题2：连续和为0后的后续判断了：
这里有两种情况，第一种简单，就是连续和直接为0的，这种的处理就是直接删除整个哈希就是，解释就是当前哈希全部无效；第二种情况，就是和不为0，终结节点为0的情况，这个看第二个注释，这个就多了东西。注意n的赋值是从当前值开始，同时开始遍历哈希，从哈希的节点后一个节点开始遍历哦，为什么是后一个节点呢，因为哈希当前节点标识是无罪的，删除需要从当前哈希节点之后到遍历的节点，这之间的哈希值是需要清楚的！
package main
func removeZeroSumSublists(head *ListNode) *ListNode {
var t int
var mem = make(map[int]*ListNode)
for l := head;l != nil;l = l.Next{
t += l.Val
if t == 0{
mem = make(map[int]*ListNode)// 问题2
head = l.Next
continue
}
if _,ok := mem[t];!ok{
mem[t] = l
continue
}
var n = t// 问题2
node := mem[n]
for v := node.Next;v!=nil&&v != l;v = v.Next{
n+=v.Val
delete(mem,n)
}
node.Next = l.Next
}
return head
}
下周计划
发布之前耽误的递归的总结，是吧，不能拉下，总结还需要提现出总体时间进度。同时还要进行链表的第二周学习，可以从链表中删去和为0的连续节点开始往下
网友评论