优享资讯 | 算法系列-链表

掘金后端 ( ) • 2022-08-06 23:07

算法系列-链表

theme: channing-cyan

以前打算每周刷一道题，从2021年12月坚持到2022年3月，坚持了3个月，后来因为其它事情太多就停止了。

坚持做一件事情，肯定是有价值的。最近总算把很多事情理顺了，那就重新开始做题吧。不过这次换一下思路，从极客时间上跟着《数据结构与算法之美》做，可以去了解一下别人对一些问题的看法，当做对教科书内容的补充。

当然，只会写一下自己有所感触的部分，否则就太耗时了。

之所以坚持做算法，原因在一道算法题-括号生成。

一、面试

面试中有很多题目是链表相关的，为什么？

写链表代码是最考验逻辑思维能力的。因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。

二、技巧

技巧一：理解指针或引用的含义
技巧二：警惕指针丢失和内存泄漏
技巧三：利用哨兵简化实现难度
技巧四：重点留意边界条件处理

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
使用next前，判断当前节点是否为nil

技巧五：举例画图，辅助思考
技巧六：多写多练，没有捷径
技巧七：操作中涉及三个指针pre cur next，将正在处理的放cur可简化操作

三、精选习题

下面有6道题，拿作者的话说是：”你只要把这几个操作都能写熟练，不熟就多写几遍，我保证你之后再也不会害怕写链表代码。“。

这些题目确实比较具有代表性，涉及到查找、删除、合并、反转节点，大部分的链表操作都由这几部分组成。我们来实现一下，在乐扣上找原题，这样裁判也有了。

代码位置：https://github.com/shidawuhen/asap/tree/master/controller/algorithm/list

3.1剑指 Offer II 027. 回文链表

这道题以前刷过一遍，不过使用的是链表转数组的方案，这次用链表方案来做。解这道题需要先找到链表中间节点，然后对链表做反转。

代码

/**
@author: Jason Pang
@desc:
@date: 2022/8/3
**/package listtype ListNode struct {
Val  int
Next *ListNode
}/**
 * @Description:
比较回文的思路，是一个从头部，一个从尾部开始对两个值做对比，比较到中点处结束
1. 写到数组里，然后在数组里比较
2. 改造成双向链表，一个往前一个往后
3. 后半部分改成从后往前的。
    需要找到中间位置
    - 方案1：遍历一遍，记录总长度，再遍历一次，就知道中间位置在哪里了
    - 方案2：快慢指针，快指针走到结束，慢指针走到中间。其实快慢指针是我们1/2,1/3等思想的具体实践
要走都走，无论奇数偶数，慢指针走到的是最后一个
然后从中间位置开始改变链表顺序
一个从头，一个从尾开始遍历，从尾部走，走到空就行
*/func isPalindrome(head *ListNode) bool {if head == nil {return true
}//找到中间位置
slow := head
fast := head
listLen := 0
for fast != nil && fast.Next != nil {if listLen%2 == 0 {
slow = slow.Next
}
fast = fast.Next
listLen++
}//从slow到fast做反向。不应该用这种方案，为啥要next、nn呢，要是用三个的话，当前的cur，然后找前一个和后一个，把自己放到中间最好处理
tmp := slow.Next
slow.Next = nil
var end *ListNode = nil
if tmp != nil {
end = tmp.Next
}for tmp != nil {
tmp.Next = slow
slow = tmp
tmp = endif tmp != nil {
end = tmp.Next
}
}//从头到中间、从尾到中间
h := headfor fast != nil {if fast.Val != h.Val {return false
}
fast = fast.Next
h = h.Next
}return true}func isPalindrome2(head *ListNode) bool {if head == nil {return true
}//找到中间位置，这种方案需要slow往后走一步
slow := head
fast := headfor fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}//从slow往后逆序
cur := slow.Nextvar pre *ListNode = nil
for cur != nil {
tmpNext := cur.Next
cur.Next = pre
pre = cur
cur = tmpNext
}//从头到中间、从尾到中间
h := headfor pre != nil {if pre.Val != h.Val {return false
}
pre = pre.Next
h = h.Next
}return true}

思路

几个月不写代码，isPalindrome虽然执行结果准确，但是写的很差，isPalindrome2就好一些。

判断是否回文，就是头指针向后移动，同时尾指针向前移动，都一样就是回文串。大方向是目标，只有确定好目标，才能填充细节，否则会毫无头绪。

3.2剑指 Offer II 022. 链表中环的入口节点

代码

/**
@author: Jason Pang
@desc:
@date: 2022/8/4
**/package list/**
这种题，如果提前没有思路的话，应该很难想出来。使用快慢指针，需要做证明，为什么快指针和慢指针肯定能碰上。
有了思路后，再做就容易多了
方向就是，你就不断的走就行，要是快指针到nil了，那就是没有，否则肯定会碰上，不要怕，就是干。

用乘法，不用除法；用加法不用减法
能自己判断出会相遇，但是相遇之后怎么做没搞出来，还是因为上面思绪错了
*/func detectCycle(head *ListNode) *ListNode {if head == nil || head.Next == nil {return nil
}
slow := head
fast := head
ptr := headfor fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Nextif slow == fast {for ptr != slow {
ptr = ptr.Next
slow = slow.Next
}return ptr
}
}return nil}

思路

这道题代码相对简单，麻烦点在于证明什么时刻会在入口点相遇。我只能证明出使用快慢指针会相遇，没有证明出相遇的时刻。

证明快慢指针会相遇：慢指针X步之后，快慢指针位置

慢指针位置：[(X+1)-(N-M)]%M

快指针位置：[(2X+1)-(N-M)]%M=[(X+1)-(N-M)]%M - X%M

所以当X对M取余为0时，两者相遇。

然后我们来看一下官方的推导：

任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)，意味我从头开始走到a结束，等于从相遇点绕(n-1)圈加c步，两个指针相遇的位置就是入口。

官方对题目抽象的更好一些，抽象的越好，越有可能解出答案；抽象能力是人的一项重要能力
图示只有最直接的距离，这些距离只需要做加法；程序中能用加法就不要用减法，能用乘法就不要用除法
有些题目，10分钟想不出方案，就不要想了

3.3 剑指 Offer 25. 合并两个排序的链表

代码

/**
@author: Jason Pang
@desc:
@date: 2022/8/4
**/package list/**
合并两个有序列表，这个不需要太多技巧，纯看能力
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
*/func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {if l1 == nil {return l2
}if l2 == nil {return l1
}//比较大小，确保l1肯定是最小的
if l1.Val > l2.Val {
tmp := l1
l1 = l2
l2 = tmp
}
l1Ptr := l1//从l1开始，如果l2比它小，就加进来
for l1Ptr != nil && l1Ptr.Next != nil {if l2 != nil && l2.Val <= l1Ptr.Next.Val {
tmp := l1Ptr.Next
l1Ptr.Next = l2
l2 = l2.Next
l1Ptr.Next.Next = tmp
}
l1Ptr = l1Ptr.Next
}//如果l2还有剩余，则补充到l1上
if l2 != nil {
l1Ptr.Next = l2
}return l1
}

思路

不需要什么技巧，纯看编码能力；画个图辅助一下

3.4 剑指 Offer II 021. 删除链表的倒数第 n 个结点

代码

/**
@author: Jason Pang
@desc:
@date: 2022/8/5
**/package list/**
删除倒数节点，这种就是干
*/func removeNthFromEnd(head *ListNode, n int) *ListNode {if head == nil {return nil
}
ahead := headfor ahead.Next != nil && n > 0 {
ahead = ahead.Next
n--
}if n > 0 {
head = head.Nextreturn head
}
bhead := head//head和ahead一起移动
for ahead.Next != nil {
ahead = ahead.Next
bhead = bhead.Next
}//删除
if bhead.Next == nil {return head
}
bhead.Next = bhead.Next.Nextreturn head
}

思路

这样直接蛮干也行，问题不大，设置哨兵能更优雅一些

最后

大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）

我的个人博客为：https://shidawuhen.github.io/

往期文章回顾：