链表逆序

痛定思痛。 2021-12-15 07:43 346阅读 0赞

链表逆序的本质就是把没一个节点原本指向的下一个节点的next指针倒转过来，指向它的前置节点

让我们从链表头部开始，建立三个临时节点的引用，分别为p1，p2，p3。它们分别指向头节点、第二个节点、第三个节点。

![20190704172453911.png][]

实现链表逆序的完整步骤如下：

1.以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。

![20190704172516448.png][]

2.三个临时节点引用p1，p2，p3分别向后移动一格位置。

![20190704172542200.png][]

3.重复第1步的工作，以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。

![2019070417260840.png][]

4.重复第2步的工作，三个临时节点引用p1，p2，p3分别向后移动一格位置。

![2019070417263356.png][]

.......

.......

5.继续像这样子迭代下去，一直到p2是空为止。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70][]

6.最后，把head节点的next指向空，成为逆序链表的尾节点。并且把p1赋值给head，让p1所在的节点成为逆序链表的头节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1][]

private static Node head;
    
        public static void reverseLinkedList() {
            if (head == null || head.next == null) return;
            Node p1 = head;
            Node p2 = head.next;
            Node p3 = null;
            while (p2 != null) {
                p3 = p2.next;
                p2.next = p1;
                p1 = p2;
                p2 = p3;
            }
            head.next = null;
            head = p1;
        }
    
        private static class Node {
            int data;
            Node next;
            Node(int data) {
                this.data = data;
            }
        }
    
        public static void main(String[] args) {/*初始化链表*/
            head = new Node(3);
            head.next = new Node(5);
            Node temp = head.next;
            temp.next = new Node(1);
            temp = temp.next;
            temp.next = new Node(4);
            temp = temp.next;
            temp.next = new Node(9);/*逆序前输出链表*/
            temp = head;
            while (temp != null) {
                System.out.println(temp.data);
                temp = temp.next;
            }/*逆序链表*/
            System.out.println("------------------");
            reverseLinkedList();/*逆序后输出链表*/
            temp = head;
            while (temp != null) {
                System.out.println(temp.data);
                temp = temp.next;
            }
        }

[20190704172453911.png]: /images/20211214/e28c385cbf6942d18ab3bffbb7313695.png
[20190704172516448.png]: /images/20211214/6101b5d9e8904697bdb314f162d21cd2.png
[20190704172542200.png]: /images/20211214/87f60e4b8e1446149205c4d2c68b9205.png
[2019070417260840.png]: /images/20211214/4f67a40e2f8346f6a1bfd74aa505282a.png
[2019070417263356.png]: /images/20211214/88e7f3878b2b4175a1a3b2052a196ac6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70]: /images/20211214/ee1ba2580c264eff9f62bc619c2ec7cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW96aHUwMzAx_size_16_color_FFFFFF_t_70 1]: /images/20211214/698fe3f9db6147118e043259a19c84d7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，346人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-链表-链表反转（链表逆序、逆置）

算法-链表-链表反转（链表逆序、逆置） 1 简单链表反转 1.1 题目出处 https://leetcode-cn.com/problems/fan-zhua

谁践踏了优雅/ 2023年07月24日 03:28/ 0 赞/ 29 阅读

相关逆序建链表和顺序建链表

本次博客也是我的第一个博客，所以肯定会有不好的地方，希望多多包涵，评论区多提提意见，帮助我改进，大家一起进步，一起努力。最近也是在学习数据结构，第一个内容就是与链表有关的，

朴灿烈づ我的快乐病毒、/ 2023年02月28日 04:12/ 0 赞/ 2 阅读

相关链表逆序操作C++版本

链表逆序操作：步骤如下：首先先记住当前节点的下一个节点的位置，因为如果将该节点插入至新节点，需要改变它的next指向然后，将当前节点的next指向new

约定不等于承诺〃/ 2023年01月01日 03:36/ 0 赞/ 250 阅读

相关单链表逆序

2、单链表逆序第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，

忘是亡心i/ 2022年09月25日 13:24/ 0 赞/ 207 阅读

相关单链表逆序

将一个单链表的内容逆序输出，考虑到当一个链表的元素打印之前将该元素的前一个元素打印，运用这个思路可以使用递归来实现该功能，（不过该方法仍然存在，问题，当链表过长会导致栈溢出问题

「爱情、让人受尽委屈。」/ 2022年07月16日 04:27/ 0 赞/ 213 阅读

相关实现链表逆序

建立一个带头结点的链表实现链表倒序 include <stdio.h> include <stdlib.h> struct node

墨蓝/ 2022年07月13日 04:50/ 0 赞/ 213 阅读

相关链表值逆序输出

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList 思路： 1）栈的出栈顺序是先进后出的，所以只需要把链表的值按顺序存到栈里

你的名字/ 2022年04月11日 13:38/ 0 赞/ 271 阅读

相关单链表反转（逆序）

面试被问到单链表反转，一脸懵逼，回来赶紧补 1、单链表的结点结构： ![2019062920353019.png][] data域：存储数据元素信息的域称

绝地灬酷狼/ 2021年12月22日 16:35/ 0 赞/ 295 阅读

相关链表逆序

链表逆序的本质就是把没一个节点原本指向的下一个节点的next指针倒转过来，指向它的前置节点让我们从链表头部开始，建立三个临时节点的引用，分别为p1，p2，p3。它们分

痛定思痛。/ 2021年12月15日 07:43/ 0 赞/ 346 阅读

相关链表逆序

不借助栈、数组等额外的空间实现链表的逆序（手动在草稿纸上绘制一下过程，很容易理解） class MyList{ int val; My

﹏ヽ暗。殇╰゛Y/ 2021年09月26日 14:52/ 0 赞/ 415 阅读