图解:单链表反转的三种方式

栏目: 数据库 · 发布时间: 5年前

内容简介:当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。单链表反转,反转后的效果如下:看起来很简单,只需要将单链表所有结点的 next 指向,指向它的前驱节点即可。引入一个栈结构,就可以实现。
图解:单链表反转的三种方式
图解:单链表反转的三种方式

当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。

单链表反转,反转后的效果如下:

图解:单链表反转的三种方式

看起来很简单,只需要将单链表所有结点的 next 指向,指向它的前驱节点即可。引入一个栈结构,就可以实现。

栈实现的链表反转

在原本链表的数据结构之外,引入一个栈( 数组也可 ),将单链表循环遍历,将所有结点入栈,最后再从栈中循环出栈,记住出栈的顺序,得到的就是反转后的单链表。

图解:单链表反转的三种方式

但是这样实现,有一个问题,它会额外消耗一个栈的内存空间,此时空间复杂度就变成了 O(n)。并且,栈会遇到的问题,使用此种方式都会遇到,例如比较常见的,栈的深度问题。

空间复杂度为 O(1) 单链表反转

接下来我们看看如何解决空间复杂度的问题。

排序 算法中,有一个概念叫 原地排序,指的是不需要引入额外的存储空间,在原数据结构的基础上进行排序 。这种 排序算法 的空间复杂度是 O(1)。例如我们常见的冒泡排序、插入排序都是原地排序算法。

这里,我们也可以在原单链表的数据结构上,进行单链表反转。

原地单链表反转,是一种很基础的算法,但是有一些在面试中遇到这道题,思路不清晰时,一时半会也写不出来。

容易出错的点在于, 指针丢失 。在转换结点指针的时候,所需结点和指针反转顺序,都很重要,一不小心,就会丢掉原本的后续指针 next,导致链表断裂。

图解:单链表反转的三种方式

在上一篇文章中,带单链表时间复杂度为 O(1) 的结点删除法中,介绍到,删除单链表的时候,需要知道前后三个结点。在单链表翻转的时候,也是这样。

当我们要对一个结点进行指针翻转的时候,我们也需要知道三个结点。

  • 待翻转的结点。

  • 待反转结点的前驱结点 prev。

  • 待反转结点的后续结点 next。

说了那么多,直接上代码。

static class Node {
    int data;
    Node next;

    Node(int data){
        this.data = data;
    }
}

static Node reverseByLoop(Node head) {
    if (head == null || head.next == null){
        return head;
    }

    Node preNode = null;
    Node nextNode = null;
    while (head != null){
        nextNode = head.next;

        head.next = preNode;
        preNode = head;
        head = nextNode;
    }
    return preNode;
}

链表翻转的所有逻辑,都在 reverseByLoop() 方法中,此处以头结点为参数,反转之后返回值为反转后的单链表头结点。

建议最好自己在 IDE 里敲一遍,加深印象。

递归实现单链表反转

单链表反转,还可以通过递归来实现,但是这里不推荐使用,大家了解一下就好了。

递归还是在借助函数调用栈的思想,其实本质上也是一个栈。没什么好说的,直接上代码。

static Node reverseByRecursion(Node head){
    if(head == null || head.next == null){
        return head;
    }

    Node newHead = reverseByRecursion(head.next);

    head.next.next = head;
    head.next = null;
    return newHead;
}

小结时刻

到这里,单链表反转的内容,都介绍完了,学算法还是要考虑多写多练,推荐大家在 IDE 中,自己手动敲一遍,加深印象。

本文对你有帮助吗? 留言、点赞、转发 是最大的支持,谢谢!

「联机圆桌」:point_left:推荐我的知识星球,一年 50 个优质问题,上桌联机学习。

公众号后台回复成长『 成长 』,将会得到我准备的学习资料,也能回复『 加群 』,一起学习进步;你还能回复『 提问 』,向我发起提问。

推荐阅读:

关于字符编码,你需要知道的都在这里 |图解:HTTP 范围请求 |Java 异常处理 | 安卓防止用户关闭动画导致动画失效 |Git 找回遗失的代码 | 阿里的 Alpha 助力 App 启动速度优化

图解:单链表反转的三种方式

以上所述就是小编给大家介绍的《图解:单链表反转的三种方式》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员修炼之道

程序员修炼之道

[美]享特 / 人民邮电出版社 / 2007-12 / 49.00元

《程序员修炼之道》适合各层次软件开发人员阅读,也适合高等院校计算机专业学生和教师阅读。一起来看看 《程序员修炼之道》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具