学习
实践
活动
专区
工具
TVP
写文章

反转链表python题解

没有白走路,每一步都要算数 文章目录 前言 一、反转链表题目 二、题目求解 1.迭代法求解 1.1 代码思路 1.2 代码图解 1.3 代码如下 2.递归法求解 1.1 代码思路 1.2 代码图解 1.3 代码如下 三、代码调试 1.题目中ListNode结构类型 2.完整程序代码 2.1 递归法求解 2.2 迭代法求解 ---- 前言 反转链表是一个超级大众题目了。 但是反转链表能够考察到知识点却是很多 比如如何使用递归,迭代来反转链表。对于初学者学习递归和迭代都是一个不错练习。 还有这种题目的数据结构都不会明确,只能以注释形式出现,很多人不能够调试,看到运行结果,很让人头疼,所以本文除了带你了解到如何使用python来求解反转链表,还会把整个pythonACM模式代码给全部显示出来演示 希望我可以一直写下去吧,见证学习成长之路也是一件很开心事情 ---- 一、反转链表题目 二、题目求解 1.迭代法求解 1.1 代码思路 给定一个链表如1->2->3->4->5 设计算法目的是把链表转成

12120

七十、反转和合并链表链表有环判断

「---- Runsen」 ❞ 最近在重新梳理学算法知识,本文为链表常见操作复习总结文章,会讲解常见链表题目实现思路及附上答案,这些题目在leetcode上对应题号也有给出,好好学习算法吧~ 单链表反转 链表中环检测 两个有序链表合并 K个有序链表合并 leetcode 对应题号:206,141,21,23 LeetCode 第 206 题:反转链表 反转一个单链表反转一个单链表需要当前节点next指针指向上一个结点pre,当前节点指针指向下一个结点,上一个结点指针指向当前节点。 通过迭代,依次反转结点指向。 新链表是通过拼接给定两个链表所有节点组成。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 从两链表第一个结点开始比较结点值,取较小者作为合并链表元素,依次进行;后面如果有一个链表为空,则直接把不为空链表接到合并链表后面

11020
  • 广告
    关闭

    有奖征文丨玩转 Cloud Studio

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    反转链表 & 876. 链表中间结点

    反转链表 力扣题目链接[1] 给你单链表头节点 head,请你反转链表,并返回反转链表。 最终pre指向就是翻转前链表尾部节点,也是翻转后链表头部,返回pre即可。 链表 /** * Definition for singly-linked list. 链表中间结点 力扣题目链接[2] 给定一个头结点为 head 非空单链表,返回链表中间结点。 如果有两个中间结点,则返回第二个中间结点。 快指针每次走两步,慢指针每次走一步,当快指针走到链表尾部时,慢指针所处位置就是链表中间节点。 包括寻找链表中间节点、检查链表是否存在环。都需要重点掌握。复杂度方面,时间复杂度是链表长度一半,也就是O(n),维护了两个常数级别的变量,因此空间复杂度是O(1)。

    10610

    单向链表花式玩法 → 还在玩反转

    单向节点 OneWayNode   虽然代码用 java 实现,但涉及到算法实现是通用,希望大家不要被开发语言所禁锢   链表反转   基本上指的是单链表反转,大家就认为是单链表反转 ,变量赋值顺序不是随便,不信你们改变下顺序试试   如果没有任何限制,反转实现方式非常多;但面试时,往往会对时间复杂度或空间复杂度做一个极致考量   这道题如果出现在面试中,那么考核点就是:时间复杂度 ,你会有惊喜,会发现有意思新大陆   回文判断   何谓回文,就是反转之后与之前本身一样,例如 a,b,b,a 、 1,2,3,2,1   针对该问题,大家第一时间想到肯定是二分法,但二分法是基于数组 ,它不适用于单链表   那么如何判断单链表回文了   那就按回文描述那样,对原链表进行拷贝,然后反转拷贝链表,再将原链表与新链表值逐一对应比较,过程类似如下   代码如下   有个数据结构, ,那有没有额外空间复杂度为 O(1) 方式了   有,同样用快慢指针,只是快指针走完后,慢指针以及它之后链表元素不是入栈,而是反转,将反转链表与原链表逐一对应比较,如下图所示   代码实现

    35820

    面试不可不会链表反转

    链表反转是面试中常考一道题,这道题看起来简单,但是能一遍写出 bug free 代码相当不容易,本文主要提供递归和迭代两种解题方法,供大家参考。 ? 题目 ? ? ? 举栗 ? 递归解法 链表具有天然递归性,一个链表例如:1->2->3->NULL,可以看成以值为 1 节点作为头节点后面挂接一个更短(以值为 2 节点为头节点)链表,即1->更短链表(以值为2节点作为头节点 ),同理以值为2节点作为头节点后面也挂接一个更更短链表(以值为3节点作为头节点);依次类推,如下图示。 有了这样思考,链表反转就可以先翻转头节点后面挂接更短链表,然后再在翻转后更短链表后面挂接之前头节点。具体如下图示: ? ? Show me the Code ? ); /* 将头节点(节点值为 1 节点)挂接在翻转之后链表后面(也就是节点值为 2 节点后面) */ head->next->next = head;

    26620

    面试必备 | 不可不会反转链表

    反转链表这题真的是面试非常喜欢考了,这题看起来简单,但是能用两种方法一遍 bug free 也是不容易,面试时候可以筛下来一大批人,无论是对 junior 还是 senior 面试都很爱考。 这是从力扣中文站上截下来,但是这个输出不太形象。 对链表反转,并不是要把它实际翻个个,只是动一动 next 指针就好了。 什么意思呢? 我们先看对数组进行反转。 数组是一个物理上连续存储数据结构,反转之后原来放 1 位置就变成了放 5. ? 但是链表并不是,因为链表在物理上是不连续,它每个单元 ListNode 是通过 next 指针连接在一起,而每个 ListNode 之间在内存里并不一定是挨着。 所以反转链表,就不是非要把 1 位置放 5,因为它们想在哪在哪。 那么怎么保证这个顺序呢? 就是 next 指针。 沿着 next 指针方向走下去,就是链表顺序。

    37620

    反转偶数长度组节点(链表

    题目 给你一个链表头节点 head 。 链表节点 按顺序 划分成若干 非空 组,这些非空组长度构成一个自然数序列(1, 2, 3, 4, …)。一个组 长度 就是组中分配到节点数目。 反转 每个 偶数 长度组中节点,并返回修改后链表头节点 head 。 - 第二组长度为 2 ,偶数,节点反转。 - 第三组长度为 3 ,奇数,没有发生反转。 - 最后一组长度为 4 ,偶数,节点反转。 - 最后一组长度为 1 ,没有发生反转。 示例 4: 输入:head = [8] 输出:[8] 解释:只有一个长度为 1 组,没有发生反转。 解题 链表反转 prevtail记录前一段末尾,L, R 记录当前段起始和结束,nthead 记录下一段开始 /** * Definition for singly-linked list.

    12220

    链表反转(递归和非递归方式)正确姿势

    1、背景 关于链表反转,很多资料讲解不够清晰,参考“无鞋童鞋”原文:https://blog.csdn.net/fx677588/article/details/72357389 理解好了很多。 1、非递归(迭代)方式 迭代方式是从链头开始处理,如下图给定一个存放5个数链表。 首先对于链表设置两个指针: 然后依次将旧链表上每一项添加在新链表后面,然后新链表头指针NewH移向新链表头,如下图所示。 首先指针H迭代到底如下图所示,并且设置一个新指针作为翻转后链表头。由于整个链表翻转之后头就是最后一个数,所以整个过程NewH指针一直指向存放5地址空间。 ListNode newHead = reverseList(head.next); // 反转 head.next.next = head; head.next =

    50120

    剑指Offer学习笔记(C#篇)-- 反转链表

    题目描述 输入一个链表反转链表后,输出新链表表头。 一 . 概念普及         关于线性表等相关概念请点击这里。 二 . 这里可以将单链表储存为数组,然后按照数组索引逆序进行反转。此处,可理解为将链表装换为顺序表,然后把队伍方向反转,但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势。         //指针是否为空判断(鲁棒性) if(head == null) { return null; } //定义新链表 head = nodeList[startIndex]; return head; }         方法二:三指针法,不做过多阐述,代码备注蛮详细。 //然后再把A和pHead都提前一位 A = pHead; pHead = B; } //循环结束后,返回新表头,即原来表头最后一个数

    17320

    《剑指offer》– 链表中倒数第k个节点、反转链表、合并两个排序链表

    : 参考博客:https://www.jianshu.com/p/e385d9c06672 1、题目: 输入一个链表反转链表后,输出新链表表头。 2、解题思路: 2-1:第一种:使用递归方式: (1)解题思路: 假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表。 如下图所示,先迭代待最后一位5,并且设置一个新节点newList作为反转链表头结点,由于整个链表反转头就是最后一个数,所以newList存放一直是反转头结点地址,将head指向地址赋值给 依次反转。。 2、解题思路: 比较两个链表第一个节点,取出最小值节点,接着再按照相同方式重复比较剩余链表节点。

    19530

    【剑指Offer专题】链表系列:从尾到头打印链表反转链表、回文链表、合并两个排序链表(C++和Python实现)

    每经过一个结点时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点值,给一个新链表结构,这样链表就实现了反转。 result.insert(0, listNode.val) listNode = listNode.next return result 剑指Offer(十五):反转链表 反转一个单链表。 输入两个单调递增链表,输出两个链表合成后链表,当然我们需要合成后链表满足单调不减规则。 1、思路 先判断输入链表是否为空指针。如果第一个链表为空,则直接返回第二个链表;如果第二个链表为空,则直接返回第一个链表。如果两个链表都是空链表,合并结果是得到一个空链表

    51810

    每日算法刷题Day14-反转链表、两个链表第一个公共结点、删除链表中重复节点

    文章目录 42.反转链表 数据范围 样例 思路 43.两个链表第一个公共结点 数据范围 样例 空节点三种写法 思路 44.删除链表中重复节点 数据范围 样例1 样例2 思路 42.反转链表 定义一个函数 ,输入一个链表头结点,反转链表并输出反转链表头结点。 样例 输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL 思路 反转链表是一个经典题目 这里先判断头节点是否为空,或者仅存在一个节点,返回即可。 输入两个链表,找出它们第一个公共结点。 在一个排序链表中,存在重复节点,请删除该链表中重复节点,重复节点不保留。

    9610

    每天一道leetcode92-反转m到n处链表

    题目 每天一道leetcode92-反转m到n处链表 分类:链表 中文链接: https://leetcode-cn.com/problems/reverse-linked-list-ii/ 英文链接 https://leetcode.com/problems/reverse-linked-list-ii/ 题目详述 反转从位置 m 到 n 链表 m等于1的话,简单,就是一个反转链表,如何反转见这篇文章,之前写过;m等于1的话,先反转m-n这些节点,反转完成以后,一开始头结点就成了最后一个节点,所以反转前把这个节点保留下来,然后反转结束以后把后面的连起来就行 ,preFirst是temp节点前一个节点,用来最后连接使用; 17-21行 因为是从第m个节点开始,所以先去找到这个第m个节点; 24-34行 就是反转链表了,不懂看这篇文章,其中要注意是,要把反转之前第一个节点也就是 m所在节点保留下来,这样方便最后连接没反转后一段部分节点; 35-36行 就是连接反转部分节点与前后两部分节点 38-50行 就是反转前1-n个节点代码,反转链表看之前链接,然后需要注意就是把第一个节点保留下来用来连接

    78310

    链表反转两种实现方法,后一种击败了100%用户!

    链表反转是一道很基础但又非常热门算法面试题,它也在《剑指Offer》第 24 道题出现过,至于它有多热(门)看下面的榜单就知道了。 ? ? 从牛客网数据来看,链表反转面试题分别霸占了【上周考过】和【研发最爱考】双重榜单,像网易、字节等知名互联网公司都考过,但通过率却低只有 30%,所以本文我们就来学习一下反转链表两种实现方法。 反转链表 描述:定义一个函数,输入一个链表头节点,反转链表并输出反转链表头节点。 反转链表 ListNode listNode = stack.pop(); // 反转第一个元素 ListNode lastNode = listNode; // 临时节点,在下面的 总结 本文我们分别使用了 Stack 和递归方法实现了链表反转功能,其中 Stack 实现方式是利用了栈后进先出特性可以直接对链表进行反转,实现思路和实现代码都比较简单,但在性能和内存消耗方面都不是很理想

    27210

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • Serverless 容器服务

      Serverless 容器服务

      弹性容器服务(EKS)是腾讯云容器服务推出的无须用户购买节点即可部署工作负载的服务模式。弹性容器服务 EKS 兼容原生 Kubernetes,支持使用原生方式购买、管理资源,并扩展支持腾讯云的存储、网络等产品,开箱即用。弹性容器服务 EKS 按容器真实使用的资源量计费,腾讯云保证用户容器的安全隔离。

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      扫码关注腾讯云开发者

      领取腾讯云代金券