猿创征文｜『牛客|每日一题』反转链表

👨‍🎓作者简介：一位喜欢写作，计科专业大三菜鸟

🏡个人主页：starry陆离

🕒首发日期：2022年8月29日星期一

🍁每日推荐：牛客网-面试神器

1.每日一题

2.测试案例

3.迭代法

3.1图解思路

迭代法解决链表反转的问题的常用方法。对于一个链表1-》2-》3。这里要注意的一个细节就是head是有值的，它指向的是链表的第一个节点。

我们定义两个临时的节点变量来进行迭代，pre始终在前，cur在后表示当前节点。

1. 初始状态，pre指向null，而cur指向头节点head（1）
2. 然后只要当前节点cur不为空，就不停的往后迭代
3. 迭代的时候我们要让cur.next=pre(null)，这是我们关键的反转步骤，因为这一步操作会修改cur的指向，所以我们要先用一个中间变量来保存cur的下一个节点。也就是代码中的cur_next（2），它始终代表cur的下一个节点。
4. 完成反转后，我们的pre和cur都要后移。这里要注意我们要先移pre，pre=cur
5. 再移cur，后移cur的时候容易错写成cur=cur.next，要注意我们已经反转了这时cur.next是null。我们应该写成cur=cur_next，因为我们的cur_next才是（2）。通过这里我们就明白了为什么我们要一个中间变量来提前保存cur的下一个节点。

复杂度分析：

时间复杂度：O(N)，其中 N 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)，常数空间复杂度

3.2完整代码

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //pre指针：用来指向反转后的节点，初始化为null
        ListNode pre=null;
        //当前节点指针
        ListNode cur=head;
        //循环迭代
        while(cur!=null){
            //Cur_next 节点，永远指向当前节点cur的下一个节点
            ListNode cur_next=cur.next;
            //反转的关键：当前的节点指向其前一个节点
            cur.next=pre;
            //后移pre
            pre=cur;
             //后移当前节点指针
            cur=cur_next;
        }
        //这里注意时返回per而不是cur,因为迭代到最后cur=null,而pre是反转后的头节点
        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

4.辅助栈法

4.1思路分析

栈在反转的题目中几乎是个万精油，因为栈本身的特点就是先进后出。

我们将链表中的所有节点都push到栈中，然后再将栈中的元素一一pop出来即可，这个思路很简单。

最后要注意的细节就是要让最后的cur.next=null。这是为什么呢？因为最后cur是指代节点（1），而节点（1）是反转前的头节点，它是指向（2），所以如果不写这一句就会构成一个局部环。

4.2完整代码

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //当前节点
        ListNode cur=head;
        //辅助栈
        Stack<ListNode> stk=new Stack<ListNode>();
        //将所有节点入栈
        while(cur!=null){
            stk.add(cur);
            cur=cur.next;
        }
        //栈为空时，链表为空
        if(stk.isEmpty()){
            return null;
        }
        //取出栈顶节点，是反转后的头节点
        ListNode pre=stk.pop();
        //逐个出栈，连成新的链表
        cur=pre;
        while(!stk.isEmpty()){
            cur.next=stk.pop();
            cur=cur.next;
        }
        //防止成环
        cur.next=null;
        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
38

5.每日推荐

📚订阅专栏：『牛客刷题集锦』

🍁每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦