前言
链表中有一些题目是需要知道并且记住对应的技巧的，有一些题目就是基本的链表技巧+手动模拟推演注意细节等。
对于需要知道并且记住对应技巧的题目会有专门的一栏进行讲解，此类题目主要有：相交链表、环形链表、回文链表等，这些必须要记住对应的破题的题眼。
本文主要是讲指定区间的链表，这类题目有一定的共性，而且常考变形题目也较多。
理论
此类题目大概是给你一个链表，让你按照某个条件，找到一个区间的开始位置，之后对这个区间一直处理直到这个区间的结束位置，当然一个链表中可能有多处这样的区间。这里涉及到的技巧在基本方法篇已经有讲，实际上就是构造、处理部分的各种组合，这里按照做题时的先后顺序归纳一下。
- 虚拟头：如果第一个节点会是区间开始位置，要用虚拟头
- 找区间开始位置，以及不符合条件时继续
- 小区间for循环处理：找到区间开始位置后，要用for循环小区间内一次性处理，直到这个区间结束
- 小区间内具体处理：重新做人法，即别用p了，直接用一个新的变量，进行赋值，避免乱，同时也能保留关键上下文。具体方案：删除（前任删除法）、反转（头插）
- 小区间处理完之后，要收摊子，要把处理的这部分接回去
基本框架流程如下
- 虚拟头
func solve(head *ListNode) *ListNode {
dummyHead := &ListNode{Next:head}
p := dummyHead
return dummyHead.Next
}
- 找区间入口
- 找到区间出口
func solve(head *ListNode) *ListNode {
dummyHead := &ListNode{Next:head}
p := dummyHead
for p.Next != nil {
if xx {
}
p = p.Next
}
return dummyHead.Next
}
- 小区间for循环处理
func solve(head *ListNode) *ListNode {
dummyHead := &ListNode{Next:head}
p := dummyHead
for p.Next != nil {
if xx {
// 找到区间入口了
tmpP := p.Next // 重新做人
for xx { // for 循环直到区间出口
}
}
p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
- 小区间处理完之后，要收摊子，要把处理的这部分接回去，注意之前的p以及p.Next指向的值，很关键
- 手动推演，即下一轮循环p的位置
func solve(head *ListNode) *ListNode {
// 1.把框架复制进来，看一下 是否能行
dummyHead := &ListNode{Next:head}
p := dummyHead
for p.Next != nil {
if xx { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件
// 找到区间入口了
tmpP := p.Next // 重新做人
// 3. 区间出口
for xx { // for 循环直到区间出口
// 4.具体处理逻辑
}
// 5.接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键
// 6.即下一轮循环p的位置：手动推演一下
}
p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
实战
接下来会使用几个题目，根据上面的套路、模版进行编码
指定区间反转链表(92)
题目：92. 反转链表 II
代码中的1、2、3即为思考编码时候的步骤
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
// 1.把框架复制进来，看一下 是否能行，这里是可行的
dummyHead := &ListNode{Next:head}
p := dummyHead
index := 0
for p.Next != nil {
index++
if index==left { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件,看来得用Index记录一下
// 找到区间入口了
// 4. 是想让我们反转，那就头插,基本套路写上
var newHead *ListNode
tmpP := p.Next // 重新做人
for index<=right { // for 循环直到区间出口
index++ // 3. 区间出口，这里肯定要++ ，具体是<=还是=可以用推演确定
cur := tmpP
tmpP = tmpP.Next
cur.Next = newHead
newHead = cur
}
// 接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键
// 5.手动推演以及p的信息，可以知道当前p是1，p.Next是2，newHead是4，tmpP是5，对应接上即可
// 要注意顺序
p.Next.Next = tmpP
p.Next = newHead
// 6.这里其实可以break了
break
}
p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
删除排序链表中的重复元素2(82)
题目：82. 删除排序链表中的重复元素 II
func deleteDuplicates(head *ListNode) *ListNode {
// 删除所有重复的元素，使每个元素只出现一次
// 1.把框架复制进来，看一下 是否能行
dummyHead := &ListNode{Next:head}
p := dummyHead
for p.Next != nil {
if p.Next.Next != nil && p.Next.Val == p.Next.Next.Val { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件
// 2. 这里就是下一个节点和下下个节点的值一样，用到了NN，额外判断nil
// 找到区间入口了
tmpP := p.Next // 重新做人
// 3. 区间出口 这里其实和if条件里的是一样的条件
for tmpP.Next != nil && tmpP.Val == tmpP.Next.Val {
// 4.具体处理逻辑，得手动推演了，
// 4.1 0 1 1 2，当前tmpP是1，最开始是符合，然后tmpP到第二个1，然后就不符合了，退出区间
tmpP = tmpP.Next // 4.2 相等就往后走
}
// 此时tmpP指向了第二个1，题目要求每个保留一次，那就只保留最后一个，
// 5.接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键
// 5.1 此时p是0，tmpP是第二个1，中间的不要了（算是删除了）
p.Next = tmpP
// 6.这里需要考虑要不要break或者Continue，手动推演一下
}
p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
删除排序链表中的重复元素(83)
题目：83. 删除排序链表中的重复元素
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
// 删除原始链表中所有重复数字的节点，只留下不同的数字
// 1.把框架复制进来，看一下 是否能行
dummyHead := &ListNode{Next:head}
p := dummyHead
for p.Next != nil {
if p.Next.Next != nil && p.Next.Val == p.Next.Next.Val { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件
// 2.1 这里的入口就是有重复的
// 找到区间入口了
tmpP := p.Next // 重新做人
// 3. 区间出口,这里就是按入口的条件一直执行到不符合要求，即为出口
for tmpP.Next != nil && tmpP.Val == tmpP.Next.Val { // for 循环直到区间出口
// 4.具体处理逻辑,不断往后走，直到找到最后一个重复的
tmpP = tmpP.Next
}
// 5.接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键.手动推演，注意这里是一个不留
// 以 0 [1,1,1,2,3] 为例，走到这里的时候 p指向0，p.Next指向第一个1，tmpP指向的是最后一个1，最终结论是 一个不留
p.Next = tmpP.Next
// 6.这里需要考虑要不要break或者Continue，即p要不要移动，这里不能移动
continue
}
p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
两两交换链表中的节点(24)
题目：24. 两两交换链表中的节点
下面这个其实写废了，想写一个支持N=任意数的，但是忽略了本题的隐藏条件，不足N个不进行调整
以及另一个重要条件，N=任意数实际上对应K个一组翻转链表这个题目，难度是Hard。
func swapPairs(head *ListNode) *ListNode {
// 1.把框架复制进来，看一下 是否能行
dummyHead := &ListNode{Next:head}
p := dummyHead
index:=0
count := 2
for p.Next != nil {
index++
if index == 1 { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件
// 2.1 这里得用一个Index记录，index可以每次置0，也可以每次求余数，这里置0
// 2.2 这里判断index == 1实际上是有点废话。可以结合下面的for循环进行优化。其实还好
// 找到区间入口了
tmpP := p.Next // 重新做人
var newHead *ListNode
// 3. 区间出口，这里同时要把Index增加的代码写上，避免忘啦
for index <= count && tmpP.Next != nil { // for 循环直到区间出口
// !!! 不足的情况没考虑啊,比如1个，或者3个
// !!! 本题 隐藏条件，不足x个不进行调整
index++
// 4.具体处理逻辑，这不就是链表逆序？!
cur := tmpP
tmpP = tmpP.Next
cur.Next = newHead
newHead = cur
}
// 5.接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键
// 5. 对于0 - 1 2 3 4 --> 0 - 2 1 3 4，此时 p指向0，p.Next是1，tmpP是3，
p.Next.Next = tmpP
p.Next = newHead
// 6.这里需要考虑要不要break或者Continue，手动推演一下，即能不能执行p = p.Next
// 6.手动推演，避免空想。 0 - 2 1 3 4 此时p是0，需要让P=1
p = p.Next.Next
index=0
continue
}
// 其实不需要这个了，写了也永远走不到 p = p.Next // 不符合条件 继续下一个
}
return dummyHead.Next
}
正确解法如下，实际上可以进一步化简，最外层的for其实可以和里面的if判断条件只保留一个。
手动推演部分这里给出画图示例，这个也是本题的复杂点，弄不好容易乱。同时需要注意 如果tmp1 := p.Next
这时候修改了tmp1.Next的值，实际上就是修改了p.Next的值，不要掩耳盗铃以为没有修改。
func swapPairs(head *ListNode) *ListNode {
// 1.把框架复制进来，看一下 是否能行
dummyHead := &ListNode{Next: head}
p := dummyHead
for p.Next != nil {
if p.Next != nil && p.Next.Next != nil { // 2. 根据题目要求写一下这个的入口条件和下面的出口条件
// 2.仅就本题而言，只需要判断 p.Next!=nil && p.Next.Next != nil 即可，之后要做的就是交换这两个
// 找到区间入口了
// 3.两个节点，一把处理了就行，不需要判断出口，
// 4.交换这俩,手动推演一下 0 - 1 2 3--> 0 2 1 3,显然需要记录2,在纸上写一下
// 5.这里交换的同时也接上去了
tmp := p.Next.Next
p.Next.Next = tmp.Next
tmp.Next = p.Next
p.Next = tmp
// 6.看一下下一轮循环p的位置，
p = p.Next.Next
// // 3. 区间出口
// for xx { // for 循环直到区间出口
// // 4.具体处理逻辑
// }
// 5.接回去 具体根据题目分析，注意之前的p以及p.Next指向的值，很关键
// 6.即下一轮循环p的位置：手动推演一下
} else {
break // 没有需要操作的了，退出
}
// p = p.Next // 不符合条件 继续下一个，不需要了
}
return dummyHead.Next
}
K个一组翻转链表
题目：25. K 个一组翻转链表
这个是Hard类型的题目，会单独写一篇文章，详细介绍思考过程和编码过程。
