進(jìn)入了7月12號(hào)了衙猪，本來預(yù)計(jì)計(jì)劃的7月份開始的第一周學(xué)習(xí)馍乙，結(jié)果到現(xiàn)在布近，整整推遲了12天的時(shí)間。還是得一直嚴(yán)于律己丝格，稍微一放松撑瞧，就會(huì)落后很多啊显蝌！
今天做了三道鏈表相關(guān)的題目：

• 合并兩個(gè)有序l鏈表
• 合并k個(gè)有序鏈表
• 反轉(zhuǎn)鏈表
• 鏈表中刪去和為0的連續(xù)節(jié)點(diǎn)

合并兩個(gè)有序l鏈表

這個(gè)是在之前面試中出現(xiàn)的題目预伺，當(dāng)時(shí)直接gg了，別面試官看出了很多問題曼尊，之前做過的題目酬诀，為什么做了一遍，就啥都沒有了呢涩禀？忘記了料滥？這確實(shí)是導(dǎo)致問題產(chǎn)生，當(dāng)時(shí)盲目的一個(gè)原因艾船，那這個(gè)原因怎么解決呢葵腹？我想了下，就做了今天這件事屿岂，總結(jié)践宴！總結(jié)這件事，給我?guī)砹撕苤庇^的兩個(gè)好處：一是爷怀，加深對(duì)題目的印象和理解阻肩，要是還能有人和你討論討論，那就效果加倍了运授；二是烤惊，及時(shí)反饋，給自己的長(zhǎng)期計(jì)劃帶來實(shí)時(shí)的動(dòng)力吁朦。
看題目吧

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
}

看著碼有點(diǎn)多捌馐摇！別怕逗宜，關(guān)鍵點(diǎn)雄右，或者是我再書寫過程中有疑惑的點(diǎn)：

• 問題1，如何返回頭結(jié)點(diǎn)：看下上面代碼的注釋纺讲，就是這個(gè)擂仍，就是這兩個(gè)變量的聲明，我發(fā)現(xiàn)使用了這個(gè)聲明之后熬甚，明顯在后續(xù)邏輯可以毫無(wú)顧忌的寫了逢渔。
• 問題2，后續(xù)節(jié)點(diǎn)的賦值：看下吧乡括，后續(xù)節(jié)點(diǎn)的賦值可以使用這種方式复局，是不是如絲般順滑

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
}

當(dāng)然冲簿，你也會(huì)使用這中反方式，看著是沒啥區(qū)別亿昏，但是完全斷開的鏈表的關(guān)系。串聯(lián)鏈表必須使用Next進(jìn)行档礁。

合并k個(gè)有序鏈表

做了第一題后角钩，再進(jìn)行這題就思路清晰了很多。當(dāng)然呻澜，做這題后我也有新的收獲暗堇瘛：
原來我這怎么寫的：

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
}

可以吧，我先說下思路羹幸，就是遍歷每個(gè)鏈表脊髓，找到最小的，然后進(jìn)行合并栅受。這個(gè)是O(n*N)的将硝，今天有突然想到了這種解法，每個(gè)都是有序的屏镊，兩兩合并不也可以嗎依疼？?jī)蓛珊喜ⅲ痪褪呛喜蓚€(gè)有序鏈表嗎而芥？對(duì)的

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
}

反轉(zhuǎn)鏈表

我只想說律罢，我也沒想到，這么簡(jiǎn)單棍丐，這里我默寫一個(gè)

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的連續(xù)節(jié)點(diǎn)

這中間也出現(xiàn)了挺多的問題
問題1：如何判斷連續(xù)和為0：
這個(gè)問題的解法很多误辑，我選擇了On的前綴+哈希，暫且這么叫吧歌逢，大致的意思就是連續(xù)求和巾钉，并且把每一項(xiàng)和哈希統(tǒng)計(jì)，當(dāng)出現(xiàn)重復(fù)的哈希時(shí)趋翻，就出現(xiàn)了和為0睛琳。很簡(jiǎn)單吧！我想的時(shí)候倒是想了很久
問題2：連續(xù)和為0后的后續(xù)判斷了：
這里有兩種情況踏烙，第一種簡(jiǎn)單师骗，就是連續(xù)和直接為0的，這種的處理就是直接刪除整個(gè)哈希就是讨惩，解釋就是當(dāng)前哈希全部無(wú)效辟癌；第二種情況，就是和不為0荐捻，終結(jié)節(jié)點(diǎn)為0的情況黍少，這個(gè)看第二個(gè)注釋寡夹，這個(gè)就多了東西。注意n的賦值是從當(dāng)前值開始厂置，同時(shí)開始遍歷哈希菩掏，從哈希的節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)開始遍歷哦，為什么是后一個(gè)節(jié)點(diǎn)呢昵济，因?yàn)楣．?dāng)前節(jié)點(diǎn)標(biāo)識(shí)是無(wú)罪的智绸，刪除需要從當(dāng)前哈希節(jié)點(diǎn)之后到遍歷的節(jié)點(diǎ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
}

下周計(jì)劃

發(fā)布之前耽誤的遞歸的總結(jié)瞧栗，是吧，不能拉下海铆，總結(jié)還需要提現(xiàn)出總體時(shí)間進(jìn)度迹恐。同時(shí)還要進(jìn)行鏈表的第二周學(xué)習(xí)，可以從鏈表中刪去和為0的連續(xù)節(jié)點(diǎn)開始往下