单链表反转

简介: 今天继续说链表,常见的算法问题有以下几种

前言


今天继续说链表,常见的算法问题有以下几种:



之前说过链表从尾开始打印链表,有的朋友说和这个单链表反转还是有区别,所以今天就看看这个类似的问题:单链表反转。


题目:单链表反转


反转一个单链表。


示例:


输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL


解法一


题目很简单,就是一个单链表,要求反转链表。


首先一个容易想到的办法就是遍历,每次把指针方向修改:


A —> B 改成 B —> A


但是在修改结点的next之前,必须更新之前的链表指向,否则就无法向后遍历,用图表示下:


0.png


public ListNode reverseList(ListNode head) {
        //新链表结点
        ListNode prev = null;
        //临时结点
        ListNode curr = head;
        //开始遍历
        while (curr != null) {
            //先设置一个临时链表结点
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }


该算法中,有两个链表:


1、新链表prev,每次改变指向之后要更新链表的结点。

2、旧链表curr,要每次更新到当前结点的next。如上图所示。


  • 开始遍历的时候,先设置一个临时链表结点指向当前结点的next,也就是上图说的情况,先记录下后面要遍历的链表结点。
  • 然后开始反转当前结点指向新链表。
  • 新链表更新到当前结点。
  • 旧链表更新到next。


时间复杂度


由于用到了遍历,所以时间复杂度就是O(n)


空间复杂度


之前说过,链表操作并没有用到另外的n大小空间,只是多了几个类似指针的链表结点,也就是常量空间,操作的还是原来的地址空间,所以空间复杂度为O(1).


解法二


还有个办法就是递归,之前说过只要遇到重复操作并且有终止条件,就可以用到递归。


那我们就先来找找这其中的重复工作。


由刚才的算法得知,从前面开始反转比较麻烦,那我们是不是可以先通过递归递到最后的结点,然后开始往前归呢?


比如先把结点递到最后一个数:


public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        return p;
    }


这样递归之后,链表结点就来到了最后一个结点,然后开始往回归,也就是把每个结点的链表反转。


假如 A -> B,我们需要反转这两个结点,你能想到什么办法呢?


很简单:


B.next=A


那B是怎么算出来的呢?


A.next=B
B.next=A 
==>
A.next.next=A


反转的方法找到了,这也就是我们需要做的重复工作:


public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        return p;
    }


但是还少了点啥?链表尾结点必须指向null,所以我们还需要再重复工作中加上在反转两个结点之后,再指向null的工作。


所以最后的算法就是:


public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }


再总结下这个递归方法:


  • :把链表指针递到尾结点
  • :从尾结点开始,每次反转相邻两个结点,并将尾结点指向null。


扩展:


其实递归方法在我们程序设计中也常常被用到。比如设计模式中的 责任链模式,就是用到了递归思想。在Okhttp的拦截器源码中就有体现~


时间复杂度


递和归相当于遍历了两次,所以时间复杂度是O(n)


空间复杂度


对于递归方法,要记住的是:


在任何时间点内存中可能存在的最大堆栈帧数等于递归树的最大深度


因为递归算法中,每个调用的方法都会生成对应的堆栈帧,保存在内存中,并且只要对这个方法的调用没有终止,那么堆栈帧就无法被释放。


从逻辑上讲,进程的堆栈是由多个堆栈帧构成的,其中的每个堆栈帧都对应一个函数调用。当函数调用发生时,新的堆栈帧被压入堆栈;当函数返回时,相应的堆栈帧从堆栈中弹出。


所以该递归方法的空间复杂度最大为O(n)


参考


https://www.cnblogs.com/cheetos/p/5405589.html 

https://time.geekbang.org/column/article/41149 

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

目录
相关文章
|
虚拟化
安装VMware提示无法访问网络位置*:\VMware\......
安装VMware提示无法访问网络位置*:\VMware\......
1180 0
|
前端开发
前端使用多张图片生成 Gif 效果(支持循环、不循环、完成回调)
前端使用多张图片生成 Gif 效果(支持循环、不循环、完成回调)
518 0
|
机器学习/深度学习 人工智能 搜索推荐
LVMH集团与阿里巴巴深化云计算合作
LVMH集团与阿里巴巴深化云计算合作
305 0
|
11月前
|
机器学习/深度学习 数据采集 人工智能
智能运维:从自动化到AIOps的演进与实践####
本文探讨了智能运维(AIOps)的兴起背景、核心组件及其在现代IT运维中的应用。通过对比传统运维模式,阐述了AIOps如何利用机器学习、大数据分析等技术,实现故障预测、根因分析、自动化修复等功能,从而提升系统稳定性和运维效率。文章还深入分析了实施AIOps面临的挑战与解决方案,并展望了其未来发展趋势。 ####
|
11月前
|
存储 负载均衡 云计算
云计算的实践:如何在企业中实现云计算转型
本文介绍了云计算的基本概念、优势及其在企业中的应用。云计算通过互联网提供计算资源,具有高灵活性和扩展性,帮助企业降低成本、提高效率。文章详细讨论了云计算转型的核心概念、实践方法和挑战,包括数据中心迁移、应用程序迁移、数据迁移和系统集成。此外,还提供了负载均衡、数据存储和处理、安全性的代码实例,并展望了云计算的未来发展趋势和面临的挑战。
227 0
|
JavaScript
【Vue面试题八】、为什么data属性是一个函数而不是一个对象?
这篇文章解释了为什么在Vue中组件的`data`属性必须是一个函数而不是一个对象。原因在于组件可能会有多个实例,如果`data`是一个对象,那么这些实例将会共享同一个`data`对象,导致数据污染。而当`data`是一个函数时,每次创建组件实例都会返回一个新的`data`对象,从而确保了数据的隔离。文章通过示例和源码分析,展示了Vue初始化`data`的过程和组件选项合并的原理,最终得出结论:根实例的`data`可以是对象或函数,而组件实例的`data`必须为函数。
【Vue面试题八】、为什么data属性是一个函数而不是一个对象?
|
存储 算法 数据可视化
Python 金融编程第二版(GPT 重译)(一)(1)
Python 金融编程第二版(GPT 重译)(一)
230 1
|
Java
【Java从入门到精通】Java switch case 语句
【Java从入门到精通】Java switch case 语句
270 0
|
物联网 Python
《HaaS物联网云端一体低代码开发课程(上)》电子版地址
由浅入深的全方位介绍物联网基础知识和网络层基础知识,直击当前物联网领域学习者所遇到的痛点问题,并基于HaaSEDUK1开发板着重介绍如何用Python轻应用开发新模式结合物联网云平台及IoTStudio对云端一体化的开发模式进行讲解
178 20
《HaaS物联网云端一体低代码开发课程(上)》电子版地址
|
存储 达摩院 云计算
排产排程问题,如何让利益最大化?(达摩院Mindopt案例)
本篇我们要讲述的案例是工厂生产相关,一个好的管理者会合理安排生产计划,让生产机器在固定的时间,不同的产品,生产效率的差异中尽可能的让工厂的利益最大化。那么面对这一问题,如果计算量比较大,该如何是好呢?
排产排程问题,如何让利益最大化?(达摩院Mindopt案例)