本期例题:LeetCode 206 - Reverse Linked List[1](Easy)
今天分享的内容是LeetCode #25 K个一组反转链表这个题目,详细内容如下:
通常来说,链表的问题从概念上讲很简单,更多时单纯的考察编码能力,而不是设计和解决算法。
反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬leetcode那道经典反转链表题出来,用十多张图去解析它,希望加深大家对链表反转的理解,谢谢阅读。
初始化:3个指针 1)pre指针指向已经反转好的链表的最后一个节点,最开始没有反转,所以指向nullptr 2)current指针指向待反转链表的第一个节点,最开始第一个节点待反转,所以指向head 3)nextnode指针指向待反转链表的第二个节点,目的是保存链表,因为cur改变指向后,后面的链表则失效了,所以需要保存 接下来,循环执行以下三个操作 1)nextnode = current->next, 保存作用 2)current->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3)pre = current, current = nextnode; 指针后移,操作下一个未反转链表的第一个节点 循环条件,当然是current != nullptr 循环结束后,current当然为nullptr,所以返回pre,即为反转后的头结点
在很多问题中,我们需要对一个链表中的节点连接进行反转,且通常需要原地进行,即不能使用额外的存储空间。这时我们可以使用就地反转链表模式,该模式本质上是一种迭代解法,流程如下图所示。首先设置一个变量 current 指向链表头部,以及另一个变量 previous 指向当前处理节点的前一个节点。下一步我们需要将当前节点 current 进行反转,将其指向前一个节点 previous,然后将 previous 指向当前节点,再将 current 移动到下一个节点,开始迭代直至遍历完成。
您在循环中为每个节点重新分配内存,这实际上是在创建原始链表的深拷贝的反转版本,而不是就地反转链表。如果只需要反转链表而不创建其副本,则无需分配新的节点内存。
首先分别设headA为p,headB为q,然后依次同时移动它们,节点遍历到尽头后,跳转到另一个头节点。
若要满足 O(1) 空间复杂度,则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问,所以这里采用的方式为,找到单链表中间元素,并反转单链表前半部分,然后与单链表后半部分进行比较是否为回文结构。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
https://leetcode-cn.com/problems/reverse-linked-list/
题目描述 输入一个链表,反转链表后,输出链表的所有元素。 思路 思路一: 迭代:将当前节点和下一节点保存起来,然后将当前节点反转。 思路二: 递归:利用递归走到链表的末端,然后再更新每一个节点的next值 ,实现链表的反转。 代码实现 package LinkedList; /** * 反转链表 * 输入一个链表,反转链表后,输出链表的所有元素。 */ public class Solution35 { /** * 递归 * * @param head
如果你和小鹿一样,刚开始对链表的操作代码实现很懵的话,不妨按照小鹿经过一个月的时间对链表相关操作以及题型的整理总结,由浅入深进行适当的练习,我相信,当你真正的练习完这些题目,不但会让你放下对链表心理上的困惑,而且对你学习其他数据结构有很大的信心和帮助!
链表的操作是数据结构中最基础的算法之一,反转列表也是一道经典的笔试题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但是如果面试者使用了额外的节点存储空间做中转,会得到一个比较低的分数。本题选自leetcode的206题,感兴趣的小伙伴可以去练习一下。206.反转链表
在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。
示例 1: 输入:head = [1, 2, 3, 4, 5] 输出:[5, 4, 3, 2, 1]
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
最近迫于生活,又去面试咯。好在魔都的就业环境还可以,面试机会总是不缺。今天闲下来了,来谈一谈我最近面试遇到的一道题,是跟反转链表相关的。
反转单链表的迭代实现不是一个困难的事情,但是递归实现就有点难度了,如果再加一点难度,让你仅仅反转单链表中的一部分,你是否能够递归实现呢?
之前的文章「递归反转链表的一部分」讲了如何递归地反转一部分链表,有读者就问如何迭代地反转链表,这篇文章解决的问题也需要反转链表的函数,我们不妨就用迭代方式来解决。
链表反转是⼀个出现频率特别⾼的算法题,笔者过去这些年⾯试,⾄少遇到过七⼋次。其中更夸张的是曾经两天写 了三次,上午YY,下午⾦⼭云,第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个 No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题,没有之⼀。 那为什么反转这么重要呢?因为反转链表涉及结点的增加、删除等多种操作,能⾮常有效考察对指针的驾驭能⼒和 思维能⼒。 另外很多题⽬也都要⽤它来做基础, 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反 转,例如两个链表⽣成相加链表。还有⼀种是链表排序的,也是需要移动元素之间的指针,难度与此差不多。接下 来我们就具体看⼀下每个题⽬。
链表反转在面试中非常常见,我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。
链表反转是一道很基础但又非常热门的算法面试题,它也在《剑指Offer》的第 24 道题出现过,至于它有多热(门)看下面的榜单就知道了。
题目 leetcode206-反转链表 分类:链表 中文链接: https://leetcode-cn.com/problems/reverse-linked-list/ 英文链接: https://leetcode.com/problems/reverse-linked-list/ 题目详述 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题? 题目详解 思路 反
上篇文章 递归反转链表:如何拆解复杂问题 讲了如何递归地反转一部分链表,有读者就问如何迭代地反转链表,这篇文章解决的问题也需要反转链表的函数,我们不妨就用迭代方式来解决。
承接第3篇文章《开启算法之路,还原题目,用debug调试搞懂每一道题》,本篇文章继续分享关于链表的算法题目。
在链表:听说用虚拟头节点会方便很多?中,我们讲解了链表操作中一个非常总要的技巧:虚拟头节点。
解题思路: 题目很简单。 既然给出的链表已经排好序,我们只需要对比当前节点的元素大小,较小的元素节点优先放入新链表中,重复操作,最后返回新链表即可:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例 2:
递归是从数学领域的数学归纳法借鉴过来的一种技术。递归代码通常比迭代代码更加简洁易懂。当任务能够被相似的子任务定义时,采用递归处理十分有效。二分排序和遍历等问题往往有简洁的递归解决方案。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
给定一个指向链表头节点的指针,任务是反转链表。我们需要通过更改节点之间的链接来反转列表。
Link list 目录: 第一部分:创建链表 1,python实现一个链表 第二部分:链表练习题 2,删除节点 3,查找中间元素 4,是否有环 5,给定一个循环链表,查找环的开始节点 6,删除链表的倒数第N个节点 7,分裂成两个链表:对半分 8,合并两个有序链表:返回一个新的有序列表 9,查找链表交集开始的节点 10,链表的插入排序 11,链表排序(O(n*lgn)) 12,对链表分区:以x的节点为基准 13,反转链表(1) 14,反转链表(2) 15,反转链表(3) 16,反转链表(4) 17,判断是否
完整高频题库仓库地址:https://github.com/hzfe/awesome-interview
解析:我们先正序遍历链表,同时将链表的值存入数组中。直到链表为空则停止遍历。最后将数组进行倒置后返回,则是最终结果。
题目 leetcode234-回文链表中文链接: https://leetcode-cn.com/problems/palindrome-linked-list/ 英文链表: https://leetcode.com/problems/palindrome-linked-list/ 难度:easy 分类:链表 题目详述 请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 题目详解 距离AC只差一个测试用例的错
单向链表的反转是一个非常常见的链表类面试题,我在刷leetcode的过程中,发现了有许多链表题目的解法,都是以反转链表为基础进行的。所以我觉得有必要记录一下。
注意,循环体设计的条件是,cur指向NULL停止,这是,tail已经为空,所以要限制一下条件.只有当还有后继即tail不为空时,才保留后继.
链表存储有序的元素集合,但不同于数组,链表中每个元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的节点(也称为指针或链接)组成,下图展示了一个链表的结构。
在链表:听说用虚拟头节点会方便很多?中,我们讲解了链表操作中一个非常重要的技巧:虚拟头节点。
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
面试锦囊系列一直有收到大家的反馈,包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等,非常高兴小破号的这些整理分享能够真正地帮助到大家
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 具体题目链接
首先,使用循环解答,不断把指向下一个的指针,指向前面的。假设链表是1->2->3->4,那么执行一次循环里面的内容的图示如下:
在头节点的后面进行插入操作,后一个插入进来的值,在前一个插入进来的值与头节点之间。
遍历链表,以 cur 表示当前节点,以 last 表示上一个节点,将 cur 的 next 指针指向 last 即可。
领取专属 10元无门槛券
手把手带您无忧上云