前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍链表反转的几种情况。

---

一、BM1反转链表

题目分析：这是最简单的一种情况，就是直接将整个链表反转。可以使用两种方式思考，分别是直接反转与递归反转。

1.直接反转

（1）首先声明两个指针，一个指向链表头，用于标记当前反转的元素，一个是空指针，用于存储最后反转后的链表；
（2）接下来把不需要反转的部分单独存储到temp中；
（3）将需要反转的元素接在pre前面，pre指向新的头节点；
（4）最后整理两个链表，pre为新链表的头，cur指向未反转的链表部分，即temp。整体流程如下：

代码如下：

function ReverseList(pHead)
{
    // write code here
    let pre = null;
    let cur = pHead;
    while(cur){
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

总结:这个方法没有什么难度，只要理清楚两个指针分别的任务即可。

2. 递归反转

（1）注：递归的时候不要陷入到一次一次的递归中，就直接认为这个函数就是可以完成这个效果即可；
（2）定义方法：ReverseList(pHead)就是可以将以pHead为头节点的链表反转过来；
（3）如果链表还有next，那就对next以后的部分进行反转，得到的反转以后的链表使用last指向它；
（4）得到新的反转链表后，要把当前节点断开，并放到反转后的链表后面，这样就完成了链表的反转。流程如下：

代码如下：

function ReverseList(pHead)
{
//     write code here
    if(pHead == null || pHead.next == null) return pHead
    var last = new ListNode();
    last = ReverseList(pHead.next);
    pHead.next.next = pHead;
    pHead.next = null;
    return last
}
1
2
3
4
5
6
7
8
9
10

总结：使用递归的方式可以减少指针的更改，需要为函数定义好功能，再选择好合适的返回值即可。

二、BM2链表内指定区间反转

题目分析：这个题也可以用普通解法和递归来考虑，感觉普通解法更加好懂，递归需要仔细分析。

1. 普通解法

（1）首先定义一个函数，函数的作用是将[A,B)左闭右开区间内的链表部分反转；
（2）然后在链表中通过循环找到这个区间，进行反转；
（3）如果左右区间相同则直接返回原链表；
（4）要记录头节点、区间前、区间后、反转后的节点，便于拼接。注意要分析一下左区间为1的特殊情况，因为它没有前面的节点，拼接上有所不同，解释如下：

代码如下：

function reverseBetween( head ,  m ,  n ){
    var node1 = head;     //左区间的前一个节点
    var node2 = head;     //右区间
    var pre = node1;      //保留头节点
    if(m==n) return head;   //如果左右节点相同，就返回原链表
    for(let i=0;i<n;i++){       //循环寻找左右区间
        if(i===m-2){     //左区间的前一个节点，便于后续拼接
            node1 = node2
        }
        node2 = node2.next;      //右节点（开区间）
    }
    if(m == 1){         //如果左区间是1
        var newnode = reverse(node1,node2)     //反转函数
        pre = newnode;         //头节点就是反转函数的头节点，因为前面已经没有节点了
    }else{
        var newnode = reverse(node1.next,node2);       //反转函数
        node1.next = newnode;          //将反转函数拼接在node1后面
    }
    
    while(newnode.next != null){       //移动指针到反转部分结束
        newnode = newnode.next
    }
    newnode.next = node2        //将最后的节点拼接在反转部分后面
    return pre;        //返回最初记录的头节点
}
//反转函数
function reverse(head,node){
    let cur = head;
    let pre = null;
    while(cur != node){
        var temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}
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

2. 递归解法

（1）首先找到需要反转的区间，通过递归将需要反转的左区间移动1位置；
（2）定义一个反转函数，函数作用是，反转1-n区间内的链表；
（3）如果是反转1-1之间的链表，则直接返回链表，并记录链表后面的值，方便后续拼接，如果不是，则依次移动节点和区间。代码如下：

function reverseBetween( head ,  m ,  n ) {
    // write code here
    var vnode = new ListNode();
    if(m == 1){
        return reverse(head,n)
    }
    head.next = reverseBetween(head.next,m-1,n-1)   //找到需要反转的区间，通过递归将需要反转的左区间移动1位置；
    return head
}
// 定义一个反转函数，函数作用是，反转1-n区间内的链表
function reverse(head,n){
    if(n == 1){
        vnode = head.next;
        return head;
    }
    var last = new ListNode();
    last = reverse(head.next,n-1);
    head.next.next = head;
    head.next = vnode;
    return last
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结普通方法和递归方式，其实从流程理解来看，普通方法更简单一些，但是从代码量来看，递归的方式更加简洁，递归的方式主要要找好出口，以及返回值。

三、BM3 链表中的节点每k个一组翻转

题目分析：这个题目还是可以使用上一题定义好的反转函数，再利用递归逐渐移动反转区间即可。
（1）定义反转区间的函数，同上一题；
（2）利用循环移动指针，确定反转区间；
（3）如果链表到结尾元素不够了，那么可以直接返回，不用再反转了；
（4）通过递归修改区间，并拼接再上次反转的后面。

function reverseKGroup( head ,  k ) {
    // write code here
    var newhead = new ListNode();
    var node = head;
    var first = head;
    for(var i=0;i<k;i++){
        if(node == null){  //链表到结尾元素不够，则不用反转了
            return head;
        }
        node = node.next
    }
    newhead = reverse(first,node)   //反转当前区间的链表
    first.next = reverseKGroup(node,k)   //通过递归修改区间并拼接在上次反转的后面
    return newhead;
}
function reverse(head,last){
    let pre = null;
    let cur = head;
    while(cur!=last){
        var temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}
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