系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线
承接上篇请查看 「数据结构&算法」必知必会系列：6. 链表（上）
本文为系列文章的链表下篇，将针对链表的一些经典问题进行实战，并总结出一些链表解题技巧。
是不是跃跃欲试了呢？开始吧 (๑•̀ㅂ•́)و✧
理解“指针”
看懂链表的结构并不是很难，但加入了指针，就很容易让人摸不着头脑。所以，要想写好链表代码，首先就要理解好「指针」。
C 语言和 Golang 中存在指针概念及对应类型，但有些语言中没有指针，取而代之的是“引用”，比如 Java、Python等。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。
重点领会以下概念：
将变量赋值给指针，实际上就是将这个变量的 内存地址赋值给指针。
反之，若 指针中存储了变量的内存地址，通过指针即能找到该变量。
下面，具体通过一些简单的单链表操作： 删除、插入、交换结点 来加深「指针」的理解。
删除结点
删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点
链表上篇，给了一个思路是改变前置 a 结点的 Next 指向即可，但是 b 的前置 a结点未知，怎么办？
这里如果对「指针」有深入认识的话，就可以想到把 b 变成 c 就成了（前提：b 非末尾结点）
一行代码搞定，是不是超简单~ （注释的方式也可，其为 LeetCode 官方解法）
/**
* 下文的示例，这段定义代码将省略
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func DeleteNode(dNode *ListNode) {
*dNode = *dNode.Next
// dNode.Val = dNode.Next.Val
// dNode.Next = dNode.Next.Next
}
https://play.golang.org/p/SsD42moMy9Y 可尝试删除末尾结点，会发生什么？
为什么不可删除末尾结点呢？自己思考下吧~
插入结点
在某个结点之后插入结点，这个也不难实现
func InsertAfterNode(iNode *ListNode, val int) {
insertNode := new(ListNode)
insertNode.Val = val
insertNode.Next = iNode.Next
iNode.Next = insertNode
}
那，在某个结点之前插入结点呢？其实就是值交换下而已
func InsertBeforeNode(iNode *ListNode, val int) {
insertNode := new(ListNode)
insertNode.Val = iNode.Val
iNode.Val = val
insertNode.Next = iNode.Next
iNode.Next = insertNode
}
交换结点
已知结点，将其与之后的结点交换（非尾结点）
有了删除了插入的经验，其实就不难了，并且可利用这两个已有方法。
比如 b 和 c 要交换（b 在 c 前），可以先在 c 节点后加入值为 b 的结点，然后删除之前的 b 结点即可。
func ExchangeNode(cNode *ListNode) {
InsertAfterNode(cNode.Next, cNode.Val)
*cNode = *cNode.Next
}
掌握了指针或引用的概念，链表代码至少可以轻松看懂，然后就开始实战吧~
以下参考： LeetCode 链表——经典问题
经典问题
反转链表
先来个经典的高频面试 🌰，如何反转一个单链表？
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
先不写，仅考虑指针变化，你会怎么做？
可能有人会想到：遍历该链表，到尾部了，将尾结点存入新链表，原链表尾结点删除，继续递归上述操作直至原链表为空。
(⊙o⊙)… 上面这种可能会是习惯数组操作的人的解法。
复杂度如何？n + n-1 + … + 1 => O(n²) ，而且额外增加了空间复杂度 O(n)，如果面试这么答大概率被 GO（GameOver😂）
链表，我们就要利用好插入/删除方便的优势，减弱查找的劣势。
一个解决方案如下：按原始顺序迭代，将迭代到的结点依次移为头结点，直至尾结点结束。
看下图应该比较容易理解（红色箭头表示需迭代的结点）：
时间复杂度为 O(n)，另，只使用了常量级的额外空间，所以空间复杂度为 O(1)
有了思路，代码也就水到渠成了（其他语言的代码思路类似，可参考 206.反转链表 ）
⚠️⚠️注意，空链表的判断
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var prev *ListNode
curr := head
for curr != nil {
tmp := curr.Next
curr.Next = prev
prev = curr
curr = tmp
}
return prev
}
反转链表 真的是面试非常喜欢考的，这题看起来简单，但是能用 两种方法 一遍 bug free 也是不容易的。
问题来了，那么你还能想到什么方式么？比如递归？ 参考 LeetCode 206题解
数组转换链表
以上示例代码中，用了穷举的方式添加链表元素，显然有点低效。
假设已知数组 [1, 2, 6, 3, 4, 5, 6] ，如何把数组转换为链表呢？
这其实不是算法范畴，但是需要理解链表结构，Golang 参考如下：
func Ints2LinkedList(nums []int) *ListNode {
if len(nums) == 0 {
return nil
}
l := &ListNode{}
t := l
for _, v := range nums {
t.Next = &ListNode{Val: v}
t = t.Next
}
return l.Next
}
其他语言实现的逻辑也类似，分析步骤如下：
- 空数组，直接返回
nil - 定义空链表 l，指针 t 指向链表内存地址，
- 遍历数组 nums
- 依次赋值 Val:v，Next: &ListNode{Val: v} 先赋Next 的内存值 =》后该内存地址存入Val 的值
- 指针 t 移至后一位，直至数组遍历完全
上述示例代码：https://play.golang.org/p/xH8TU7_1Zsd；参考：大佬的解法
个人原始解法：https://play.golang.org/p/CwRYrDxUPFZ；和大佬相形见绌呀
问题来了，那么链表如何转数组呢？有兴趣的可以研究下哦 (づ｡◕‿‿◕｡)づ
移除链表元素
删除链表中等于给定值 val 的所有结点。
输入: 1->2->6->3->4->5->6->NULL, val = 6 输出: 1->2->3->4->5>NULL
这里提供两种思路：
第一种，遍历查找，找到 ==val 的结点，删除即可（即前置结点 .Next 指向后一个结点的地址，即 CurrentNode.Next.Next）
但是，这种方式须注意，头结点的指向变化（仅当 head.Val == val 的时候）
参考 Golang 代码如下（其他语言可参考 237.删除链表中的节点 ）：
func RemoveElements(head *ListNode, val int) *ListNode {
for head != nil && head.Val == val {
head = head.Next
}
if head == nil {
return head
}
curr := head
for curr.Next != nil {
if curr.Next.Val == val {
curr.Next = curr.Next.Next
} else {
curr = curr.Next
}
}
return head
}
第二种，递归方式，略有点难理解，可参考 LeetCode 题解 ，其中也提供了其他的一些方式方法
func RemoveElements(head *ListNode, val int) *ListNode {
if head == nil {
return head
}
head.Next = RemoveElements(head.Next, val)
if head.Val == val {
return head.Next
}
return head
}
奇偶链表
给定一个单链表，把所有的奇数结点和偶数结点分别排在一起。请注意，这里的奇数结点和偶数结点指的是结点编号的奇偶性，而不是结点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为结点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数结点和偶数结点的相对顺序。 链表的第一个结点视为奇数结点，第二个结点视为偶数结点，以此类推。
同样，延续迭代的思路，先画图如下（主要思考指针如何移动，结点如何操作）
我们可以先分离 奇数链 和 偶数链，然后将其串联起来，参考下图，参考 328.奇偶链表
跟着思路逻辑，直接开干吧~
func OddEvenList(head *ListNode) *ListNode {
if head == nil {
return head
}
evenHead := head.Next
odd := head
even := evenHead
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = evenHead
return head
}
回文链表
请判断一个链表是否为回文链表。234.回文链表
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
方法一：记录下链表的值，可考虑链表转数组（之前的引申思考）。然后，遍历对比数组的值即可。
这个方式，复杂度 O(n) + O(n/2) => O(n)，空间复杂度 +O(n)
func isPalindrome(head *ListNode) bool {
vals := []int{}
for head != nil {
vals = append(vals, head.Val)
head = head.Next
}
n := len(vals)
for i, v := range vals[:n/2] {
if v != vals[n-1-i] {
return false
}
}
return true
}
方法二：递归实现，但是，时间和空间复杂度仍需要 O(n)
func isPalindrome(head *ListNode) bool {
frontPointer := head
var recursivelyCheck func(*ListNode) bool
recursivelyCheck = func(curNode *ListNode) bool {
if curNode != nil {
if !recursivelyCheck(curNode.Next) {
return false
}
if curNode.Val != frontPointer.Val {
return false
}
frontPointer = frontPointer.Next
}
return true
}
return recursivelyCheck(head)
}
方法三：将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较
比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。
然后呢，怎么搞？使用双指针记录&对比，空间复杂度可降为 O(1) 。哎，好累 ヽ(￣▽￣)و
func reverseList(head *ListNode) *ListNode {
var prev, cur *ListNode = nil, head
for cur != nil {
nextTmp := cur.Next
cur.Next = prev
prev = cur
cur = nextTmp
}
return prev
}
func endOfFirstHalf(head *ListNode) *ListNode {
fast := head
slow := head
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func isPalindrome(head *ListNode) bool {
if head == nil {
return true
}
// 找到前半部分链表的尾节点并反转后半部分链表
firstHalfEnd := endOfFirstHalf(head)
secondHalfStart := reverseList(firstHalfEnd.Next)
// 判断是否回文
p1 := head
p2 := secondHalfStart
result := true
for result && p2 != nil {
if p1.Val != p2.Val {
result = false
}
p1 = p1.Next
p2 = p2.Next
}
// 还原链表并返回结果
firstHalfEnd.Next = reverseList(secondHalfStart)
return result
}
技巧总结
熟练掌握指针
要想写对链表代码，首先就要理解好「指针」。如果想追本溯源，计算机系统的内存使用值得你去探索。
针对链表指针掌握，本文开头就有重点说明和举例，不熟练的就多练，温故而知新。
注意指针丢失
⚠️⚠️注意，空指针引用报错，如 Golang 就可能报错如下：
指针混乱是比较容易出现的问题，初学者包括我。。。也常常会混乱。
比如，在插入结点，一定要注意操作的顺序。
对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。这就更应该引起重视了
同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。
留意边界处理
代码在一些边界或者异常情况下，最容易产生 Bug。在代码编写过程中，是否有注意检查边界条件？这很重要，往往决定了开发能力的好坏，这也是面试中，面试官一定会注意考察的点。
所以，通常在写方法或函数中，一开始就会判空。（可看上之前的示例）
检查链表代码是否正确的边界条件通常有以下几个：
- 链表为空时
- 链表只包含一个结点时
- 链表只包含两个结点时
- 代码逻辑在处理头结点和尾结点的时候
其实，此类“检查边界”的套路适用于几乎所有代码检测，这也是「边界值测试」的范畴。
尽可能多分析会遇到哪些边界情况或者异常情况，遇到了又该如何应对，这样写出来的代码才够健壮！
画图辅助思考
复杂的算法题，往往需要先举例以及画图，尤其是类似链表这种包含指针的。
打草稿不可耻，画的好看不好看都不重要，能解决问题才是硬道理。
上面有个例子特意配了张手稿，有没有注意到呢？多色笔辅助能帮助我们理清思路（尤其是双指针）。
有关双指针（快、慢指针）准备之后特别整理一章节做类似算法技巧的整合。
其实呢，这种题就是初看很可能没有思路，但一旦知道了就不容易忘。
如判断链表是否有环，以及环的入口等，如 141.环形链表 等
其次，写完代码后，也可以举几个例子，画在纸上，照着代码走一遍，很容易就能发现代码中的 Bug。
递归思维方式
链表中的很多操作，都可以使用「递归」的逻辑思维方式来完成。
其实，「递归」也是需要练习的，这里只是在例子中蜻蜓点水一下。递归的 时间空间复杂度的理解和分析相对更麻烦一些（头都大了…）。
准备之后特别整理出「递归算法」，主要讲解递归的算法思路和复杂度分析。学完了之后再来看这些链表的题，用递归的方式再来一遍吧~