反转链表系列

前言

反转链表这种问题，是一种堆栈的思想，就是走过的路，我都要记录下来。这样子我回头才知道先到那个码头，再到那个衙门。这是贯穿整个反转链表系列题目的核心思想。

链表中需要特别注意的就是指针的指向问题与null的判断，是整个代码的核心。在链表题目当中，头节点是十分重要的切入口，我们经常会使用虚拟节点进行头节点的保护，这是一种非常好用的办法，以免在后面的逻辑中不知道头节点在那个位置。

整体链表反转（普通型）

###反转链表

按照堆栈的思想，这道题可以有三种做法

方法1 ：自己构建堆栈，保存顺序信息

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //从遍历的方式去做
        if(head==null || head.next==null)
        {
            return head;
        }
        //使用辅助堆栈
        Stack<ListNode> help=new Stack<>();
        ListNode newhead=new ListNode();
        while(head.next!=null)
        {
            help.push(head);
            newhead=head.next;
            head=head.next;
        }
        ListNode temp=newhead;
        while(!help.empty())
        {
            temp.next=help.pop();
            temp=temp.next;
        }
        temp.next=null;
        return newhead;
    }
}
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

时间复杂度：O(n)；空间复杂度：O(n)
上面方法的弊端在于引入辅助堆栈，导致空间复杂度过高

方法2 采用滚动数组的方式降低空间复杂度

依次反转，难点在于循环结束条件的判断以及反转后的头节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null)
        {
            ListNode 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

时间复杂度O(n)；空间复杂度O(1)。

方法3：递归方法，不显式构建堆栈

说实话，递归方法很难理解。本身递归的做法，我们一般都会其形与意，而不深究其内部调用
递归，有”递“还要有”归“，所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，否则会一直调用自己，造成死循环，从而栈内存溢出。也就是说，我们需要找出当方法的参数符合某一条件时，递归结束，之后把结果返回。
递归的套路甚至于其解决问题的思路都是一样的，在本题中越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
        {
            return head;
        }
        ListNode temp=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对于这个递归方法的理解由以下的前提：
递归方法的使用充分利用值传递，利用内存地址之间的传递。
值传递的重点在于：AB两空间存放相同的变量，修改A则B跟着变化。
我们在通过双指针进行递归遍历的时候，是从前往后依次反转链表。而对于递归形式的反转链表是从后向前依次反转链表。
链表例子：1->2->3->4->5
分析：
什么时候开始归呢？当我们出现head或者head.next都等于null的时候，就开始归，第一次触发结束条件时head=5->null，返回head=5->null并且赋值给temp,这个时候我们注意

  ListNode temp=reverseList(head.next);
1

这句话中的head是什么？是4->5->null，这样递进去才是head=5->null触发结束的判断，那么执行head.next.next=head就会使得5指向4，并且出现循环指向：
5->4->5->4->5->4…（注意这时候的temp的值与节点5是在同一个位置上的)
后面一旦执行head->next=null,就会使得temp=5->4->null,那么最后一行语句返回temp，再次归到语句

  ListNode temp=reverseList(head.next);
1

并且直接将返回的temp赋值给当前temp，并且这时候的head=3-4->null,然后再次参照上面的执行依次执行，这一次的temp会返回5->4->3->null。
所以我们的一个困惑就解决了，我曾经想过这样一个temp第一个返回的是5元素的位置，刚好是我们想要的反转后的链表的头节点，那么在后面的递归程序中不会改变吗？通过我们的分析可以看到，多次递归只是在他后面加上了链表，而每次返回的都是原来temp的头节点，只是其后面元素的值发生了变化。

区域链表反转

反转链表II

方法1 普通的迭代方法

注意此方法中dummpy节点的使用，大幅度降低了需要讨论的复杂程度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void myreverse(ListNode* head)
    {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr)
        {
            ListNode* t=cur->next;
            cur->next=pre;
            pre=cur;
            cur=t;
        }
    }
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //定义dummpy节点
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        //找到left的上一个节点
        ListNode* pre=dummy;
        for(int i=0;i<left-1;i++)
        {
            pre=head;
            head=head->next;
        }
        ListNode* successor=pre;
        // cout<val;
        //找到right节点本身
        for(int i=left-1;i<right;i++)
        {
            successor=head;
            head=head->next;
        }
        // cout<val;
        //现在要打断链表之间的连接，这又是一项新操作
        ListNode* leftnode=pre->next;
        ListNode* rightnode=successor->next;
        pre->next=nullptr;
        successor->next=nullptr;
        myreverse(leftnode);
        //现在再把他们连接起来,按照地址是不会变的原则
        pre->next=successor;
        leftnode->next=rightnode;
        return dummy->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

方法2：多层次的递归方法

为什么说这一道题的递归是多层次的，因为直接去解决这道题是复杂的，但是如果我们可以将这道题分解出来，就可能解决出来
解决这道题需要在一道题的基础上去做
基础题目：反转链表的前n个元素
最终达到的效果(图片来源：labuladong)：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
	//全局唯一
	ListNode successor = null; // 后驱节点
    public ListNode reverseListN(ListNode head,int n) {
        if(n==1)
        {
            //这个元素只有在回溯阶段才用的上
        	successor=head.next;
            return head;
        }
        ListNode temp=reverseListN(head.next,n-1);
        head.next.next=head;
        head.next=successor;
        return temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在基础题目的基础上，我们来解决反转链表区域间元素的题目。这时候，我们思考怎么样从基础题目向这道题转化，当left=1时，这道题就简化为了基础题目，所以这可以作为我们的base case条件，那么我们怎么样操作才能越来越向着base case转化

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}
1
2
3
4
5
6
7
8
9

当然这道题，我们可以先找到数字下标m,n所对应的链表节点，进而反转两个节点之间的链表，在同前后节点相链接起来。

几个一组反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null)
        {
            return null;
        }
        ListNode a=head;
        ListNode b=head;
        for(int i=1;i<=k;i++)
        {
            if(b==null)
            {
                return head;
            }
            b=b.next;
        }

        ListNode newHead=reverseAB(a,a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }
    public ListNode reverseAB(ListNode head,ListNode a,ListNode b)
    {
        if(head==b||head.next==b)
        {
            return head;
        }
        ListNode temp=reverseAB(head.next,a,b);
        head.next.next=head;
        head.next=null;
        return temp;
    }

}
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

这一道如果直接拿到手是比较困难的，但是如果我们从上面的简单的反转链表，就可以想到分步解决这道题，首先是反转两个节点之间的链表，然后将整个问题化简为多个反转节点之间链表的问题从而解决该问题。
当然这道题，完全可以用循环的方式去解决，只要记录好节点之间的关系就行。
这道题在debug的时候提醒我们，一但程序中的某个值出现null，会直接引发break崩溃。
所以我们在此题中，利用for循环来找b的节点的时候，最好找到要反转的尾节点的下一个节点，这样才不会引发nullponiter的错误，当然我们找到尾节点的下一个节点的时候，反转两个节点之间链表的程序的节点也要做相应的调整。

    public ListNode reverseAB(ListNode head,ListNode a,ListNode b)
    {
        if(head==b.next||head.next==b.next)
        {
            return head;
        }
        ListNode temp=reverseAB(head.next,a,b);
        head.next.next=head;
        head.next=null;
        return temp;
    }
1
2
3
4
5
6
7
8
9
10
11

我们直接用b做判断就可，不需要next了。

    public ListNode reverseAB(ListNode head,ListNode a,ListNode b)
    {
        if(head==b||head.next==b)
        {
            return head;
        }
        ListNode temp=reverseAB(head.next,a,b);
        head.next.next=head;
        head.next=null;
        return temp;
    }
1
2
3
4
5
6
7
8
9
10
11

在idea中debug的时候，我们发现在递归反转链表的基本框架下（就是上面这段代码）
head.next.next=head;
会引起大量的内存消耗，因为会出现无限递归形式的链表5->4->5->4->…
所以必须要有head.next=null这段代码。