# 链表进阶 - 论递归在链表中的作用
# 前言
初次接触链表的时候，一方面在改变指针的时候容易出现问题导致链表出现环，当然之后只要涉及改变指针就靠画图理顺指针改变顺序解决了这个问题，另一方面链表与数组不一样的点在于链表无法回退，这时递归登场了，因为递归有回溯的过程，所以只要将链表的下一项当作参数，那么在回溯的时候自然就会进行回退。使用递归能很轻松地解决蛮多链表的问题。以下是一些用递归解决链表的类型题目。
# 一 、反转链表
这类型题目主要是需要在外面设置一个变量储存链表，然后将链表的下一项当作递归的参数，当到达要交换的最后一个节点时就要 return，然后在回溯的部分交换，外面的链表记得在交换后往前走，里面的链表在返回上一层函数的时候会自动回退，这就起到了前后两边交换节点。同时反转链表有两种情况，一种是反转相邻的节点，另一种是反转的节点隔一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| var reverseList = function(head) {
if(!head||!head.next) return head //如果链表为空或者只有一项return原链表就行
/*
这里用到了虚拟头节点，因为第一个头节点也要交换如果设置虚拟头节点方便交换头节点，另外也需要在外面设置一个变量一个正向移动，另一个在回溯中逆向移动两个交换节点就能实现链表反转。
*/
let cur = new ListNode(0,head),node = cur
const dfs=(list)=>{
//因为最后一个节点要交换，交换节点需要到前一个节点，所以这里到最后一个节点就return这样回溯部分就从倒二个节点开始回退
if(!list.next) return
//一旦交换成功就return true，一旦return的结果是true就立马return true防止继续进行回溯部分。导致已经交换过的节点继续交换。
if(dfs(list.next)) return true
//最后一次交换有两种情况，一种就是这个，交换节点挨着。
if(cur.next==list){
let temp = cur.next
cur.next = cur.next.next
temp.next = cur.next.next
cur.next.next = temp
return true
}
//大部分交换时，交换的节点都隔着节点
let temp1 = cur.next,temp2=list.next
cur.next = cur.next.next
list.next = list.next.next
temp2.next = cur.next
cur.next = temp2
temp1.next = list.next
list.next = temp1
cur = temp2
//如果要交换的节点之间隔着一个节点，交换后cur的下个节点就是list这时该赶紧return。
if(cur.next==list) return true
}
dfs(node)
return node.next //最后return记得不要带上自己设置的虚拟头节点。
};
|
这题与上面一题差别在于，不是整个链表反转。因此在在用递归反转链表时，需用 while 循环到达需要反转的链表节点前面，同时递归函数增加一个参数用于判断是否到达了最后一个需要反转的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| var reverseBetween = function(head, left, right) {
if(!head.next||left==right) return head
let node = new ListNode(0,head) //这里同样需要设置虚拟头节点，因为有可能left为1，头节点需要反转。
let l=node,r=node
//用while循环让l和r达到需要交换的第一个节点前。
while(left>1){
l=l.next
r=r.next
left --
right --
}
//下面代码与上题一致，无非就是多了参数，判断条件有变，交换部分的代码一致。
const dfs =(r,right)=>{
if(right==0) return
if(dfs(r.next,right-1)) return true
if(l.next==r){
l.next = l.next.next
r.next = l.next.next
l.next.next = r
return true
}
let temp1=l.next,temp2=r.next
l.next = l.next.next
r.next = r.next.next
temp1.next = r.next
r.next = temp1
temp2.next = l.next
l.next = temp2
l = temp2
if(l==r||l.next==r) return true
}
dfs(r,right)
return node.next
};
|
这题相比于上一题在于不只反转一次。反转的代码依旧可以用上面代码不过判断条件复杂一些。另外最后一组的链表长度如果小于倒数第二组的长度，这时如果长度为偶数则还要反转，而不是最后一组是偶数组才要反转，一开始还理解错误题目来着。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| var reverseEvenLengthGroups = function(head) {
if(!head||!head.next||!head.next.next) return head
let cur = head,outside = head,inside = head,index = 2
const dfs =(list,num,k)=>{
/*
判断条件相比之前的题有亿点多，一共有四种情况。分为两大类一类是没走完，另一类是走到末尾了。反转链表的代码还是一样。
没走完的情况：
1.这时list不为空，num为0。如果当前所在组是奇数，k%2为1 这时不该反转链表，也是不执行回溯部分代码，需return一个值，这里我return-1，下面接收值，如果是-1就立即return-1
2.如果当前所在组是偶数，k%2为0 这时该反转链表，这里return不return值都行。反正要执行下面回溯部分的反转链表的代码。
走完的情况：
3.如果剩余链表数为偶数的话，k-num%2为0，这时要执行回溯部分的代码反转链表，记得这时需到最后一个链表后再return，因为最后一个要反转，所以反转时需到倒数第二个链表的位置。所以这里的判断条件是!list.next而且这个条件需在!list之下不然会出现list为空所以没有list.next的错误。
4. 如果剩余链表数为奇数的话，这时list为空，同样return一个值，下面用一个变量接住后，加个判断条件return出去，防止执行回溯部分的代码。
*/
if(!list) return false
if(!list.next&&(k-num)%2==0) return
if(num==0&&k%2==0) return
if(num==0) return -1
let res = dfs(list.next,num-1,k)
if(res==true){
return true
}else if(res ==false){
return false
}else if(res==-1){
return -1
}
if(outside.next==list){
let temp = list
outside.next = outside.next.next
temp.next = outside.next.next
outside.next.next = temp
return true
}
let temp2 = list.next,temp1 = outside.next
list.next = list.next.next
outside.next = outside.next.next
temp2.next = outside.next
outside.next = temp2
temp1.next = list.next
list.next = temp1
outside = temp2
if(outside.next == list) return true
}
while(cur){
if(dfs(inside,index,index)===false) return cur
//注意递归运行完后这里的outside会发生变化，需将inside赋值给outside
outside = inside
let k = index
while(k>0){
if(!inside||!outside) return cur
inside = inside.next
outside = outside.next
k--
}
if(!inside||!outside) return cur
index++
}
return cur
};
|
这题和上面一样也需要多次反转，我看评论区发现，字节似乎很喜欢考这题，不过老实说这题感觉难度和上面差不多甚至比上题可以还略微简单结果这题是困难上题是一般。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| var reverseKGroup = function(head, k) {
if(k==1) return head
let node = new ListNode(0,head),l=node,r=node
const dfs=(r,num)=>{
//判断条件有两个一个是剩余链表不足k个这时num大于1，r为空，无需反转。另一个是num为0需反转。
if(!r) return false
if(num==0) return
let res = dfs(r.next,num-1)
if(res==false){
return false
}else if(res==true){
return true
}
if(l.next==r){
l.next = l.next.next
r.next = r.next.next
l.next.next = r
r = l
return true
}
let temp1 = l.next,temp2=r.next
l.next=l.next.next
r.next=r.next.next
temp2.next = l.next
l.next = temp2
temp1.next = r.next
r.next = temp1
l = temp2
if(l==r||l.next==r) return true
}
while(r){
dfs(r,k)
//和上面一样递归反转后l的链表会改变，这时需将r赋给l。
l = r
let number = k
while(number>0){
if(!l) break
l = l.next
r = r.next
number--
}
}
return node.next
};
|
# 二、回文链表
这个没什么好说的，记得外面的链表也要移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var isPalindrome = function(head) {
let cur = head
if(!head||!head.next) return true
const dfs=(list)=>{
if(!list) return
let res = dfs(list.next)
if(res){
return true
}else if(res==false){
return false
}
if(list.val!=cur.val) return false
if(cur.next==list||cur.next.next==list) return true
//记得外面的链表也要往前移动。
cur=cur.next
}
return dfs(cur)
};
|
# 三、删除链表中满足某个条件的值
递推部分用哈希表获取链表各个值极其个数，回溯部分再根据哈希表删除重复的元素即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| let map = new Map(),cur = head
const dfs =(list)=>{
// 当链表为空时再return而不是到链表倒数第一位再return，不然的话递推部分会记录倒数第一个值
if(!list) return
if(map.has(list.val)){
map.set(list.val,map.get(list.val)+1)
}else{
map.set(list.val,1)
}
dfs(list.next)
if(!list.next) return // 如果是倒数第一个就直接return到上一层也就是倒数第二个，倒数第一个位置删除不了节点。
let num = map.get(list.next.val)-1
map.set(list.next.val,num)
if(num>=1){
list.next = list.next.next
}
}
dfs(cur)
return cur
|
和上题差不多不过这里头节点可能会删除所以可以整一个虚拟头节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| var deleteDuplicates = function(head) {
let map = new Map(),cur = new ListNode(false,head)
const dfs=(list)=>{
if(!list){
let key = map.keys()
for(let i of key){
if(map.get(i)==1) map.delete(i)
}
return
}
if(map.has(list.val)){
map.set(list.val,map.get(list.val)+1)
}else{
map.set(list.val,1)
}
dfs(list.next)
if(!list.next) return
if(map.has(list.next.val)) list.next =list.next.next
}
dfs(cur)
return cur.next
};
|
# 二、回文链表
这个没什么好说的，记得外面的链表也要移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var isPalindrome = function(head) {
let cur = head
if(!head||!head.next) return true
const dfs=(list)=>{
if(!list) return
let res = dfs(list.next)
if(res){
return true
}else if(res==false){
return false
}
if(list.val!=cur.val) return false
if(cur.next==list||cur.next.next==list) return true
//记得外面的链表也要往前移动。
cur=cur.next
}
return dfs(cur)
};
|
# 三、删除链表中满足某个条件的值
递推部分用哈希表获取链表各个值极其个数，回溯部分再根据哈希表删除重复的元素即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| let map = new Map(),cur = head
const dfs =(list)=>{
// 当链表为空时再return而不是到链表倒数第一位再return，不然的话递推部分会记录倒数第一个值
if(!list) return
if(map.has(list.val)){
map.set(list.val,map.get(list.val)+1)
}else{
map.set(list.val,1)
}
dfs(list.next)
if(!list.next) return // 如果是倒数第一个就直接return到上一层也就是倒数第二个，倒数第一个位置删除不了节点。
let num = map.get(list.next.val)-1
map.set(list.next.val,num)
if(num>=1){
list.next = list.next.next
}
}
dfs(cur)
return cur
|
和上题差不多不过这里头节点可能会删除所以可以整一个虚拟头节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| var deleteDuplicates = function(head) {
let map = new Map(),cur = new ListNode(false,head)
const dfs=(list)=>{
if(!list){
let key = map.keys()
for(let i of key){
if(map.get(i)==1) map.delete(i)
}
return
}
if(map.has(list.val)){
map.set(list.val,map.get(list.val)+1)
}else{
map.set(list.val,1)
}
dfs(list.next)
if(!list.next) return
if(map.has(list.next.val)) list.next =list.next.next
}
dfs(cur)
return cur.next
};
|
前缀和 + 链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var removeZeroSumSublists = function(head) {
let arr = [],cur = new ListNode(0,head),index = -1
const dfs =(list,num)=>{
if(!list) return
if(arr.length!=0){
arr.push(arr[num-1]+list.val)
}else{
arr.push(list.val)
}
dfs(list.next,num+1)
let k = arr.indexOf(arr[num+1])
if(k!=num+1&&index==-1) index = k
if(index!=-1) list.next = list.next.next
if(index==num) index = -1
}
dfs(cur,0)
return cur.next
};
|
