【算法】链表反转

这篇具有很好参考价值的文章主要介绍了【算法】链表反转。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

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

数据范围:
要求:空间复杂度 ,时间复杂度 。

如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。文章来源地址https://www.toymoban.com/news/detail-532318.html

思路

  • 每次反转需要修改两个指针
  • 最终需要返回头节点,所以需要有一个节点始终指向头节点

代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        if(head ==null){
            return null;
        }
        ListNode pre=null;
        ListNode next=null;

        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;

        }

        return pre;
    }
}

到了这里,关于【算法】链表反转的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

    还不清楚链表的码喵们可以看看前篇关于链表的详解 既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路:遍历整个表,访问每个表的值并且删除再将nex

    2024年02月22日
    浏览(51)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析: 完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 (1)定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(50)
  • 【JavaScript数据结构与算法】字符串类(反转字符串中的单词)

    个人简介 👀 个人主页: 前端杂货铺 🙋‍♂️ 学习方向: 主攻前端方向,也会涉及到服务端(Node.js) 📃 个人状态: 在校大学生一枚,已拿多个前端 offer(秋招) 🚀 未来打算: 为中国的工业软件事业效力 n 年 🥇 推荐学习:🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2023年04月09日
    浏览(91)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(48)
  • 【算法与数据结构】链表

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

    2024年02月03日
    浏览(45)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(46)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(59)
  • 【数据结构与算法】双向链表

    作者:旧梦拾遗186 专栏:数据结构成长日记   带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。 现在我们来通

    2024年02月11日
    浏览(58)
  • 【数据结构和算法】奇偶链表

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一:分离节点后合并 三、代码 3.1 方法一:分离节点后合并 四、复杂度分析 4.1 方法一:分离节点后合并 这是力扣的 328 题,难

    2024年01月20日
    浏览(50)
  • 算法与数据结构之链表

    链表的定义,相信大家都知道,这里就不赘述了只是链表分单向链表和双向链表,废话不多说,直接上代码 链表节点的定义: 打印链表的两种方式: 翻转单向链表:核心思路是先断开连接,再将next指向前继节点,为了避免断开之后,找不到前继节点,需要用一个临时变量记

    2024年02月05日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包