【算法面试必刷JAVA版一】反转链表

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

🚴🏻‍♂️个人主页：莫逸风

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：BM1 反转链表

描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

思路：

迭代：调整每一个节点的指向

1. 创建pre,cur,next三个指针，使得pre指向null，cur指向头节点，next不赋值。
2. cur节点不为空，则其next需要指向前一个节点即pre节点，在改变cur.next之前，先用next节点记录下cur.next。

代码：

public class BM01 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(5);
        ListNode listNode4 = new ListNode(7);
        ListNode listNode5 = new ListNode(9);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode curListNode = listNode1;
        while (curListNode!=null){
            System.out.println(curListNode.val);
            curListNode = curListNode.next;
        }
        curListNode = ReverseList(listNode1);
        while (curListNode!=null){
            System.out.println(curListNode.val);
            curListNode = curListNode.next;
        }
    }

    public static ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while (cur!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
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

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101