单链表反转是面试中常考的一道题,这道题看起来简单,但是能一遍写出 bug free 的代码相当不容易,本文主要提供递归和迭代两种解题方法,供大家参考。
比如有一个链表是这样的,1->2->3->4->5,反转后成为 5->4->3->2->1。请实现函数
示例 1: 给定单向链表 1->2->3->4->5,反转后为 5->4->3->2->1。
二面基本是场景设计题,具体忘了,有一说一百度面试体验很好,和面试官一起探讨解决的办法
可以看到,一个链表的节点包含数据域和指向下一个节点的引用,链表最后一个节点指向null(空区域)。
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
01 — 单链表 链表玩的是指针操作,非常容易出错,尽管看似很简单。 先定义一种单链表,JAVA(或C#)描述的数据结构如下: public class CLinkedList { public int val { get; set; } //简化起见,数据域直接定义为 int public CLinkedList next { get; set; } //next域,这就是链到下一个元素,或者理解为下一个元素的引用 } 再用最易理解的方式,初始
之前说过链表从尾开始打印链表,有的朋友说和这个单链表反转还是有区别,所以今天就看看这个类似的问题:单链表反转。
输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] 示例 2:
初拿到这题,很容易联想到反转系列用java的api中提供了几个类似的api如Collections.reverse()和StringBuilder.reverse()。他们提供了直接对集合、字符串的反转api。需要的就是根据链表构建集合,再将集合反转,反转后再重新构建链表指向关系。代码如下:
f(n) = f(n-1) + f(n-2); f(1) = 1, f(2) = 1
在看具体算法之前,有必要先弄清楚链接反转的原理以及需要哪些指针。举例而言,有一个三个不同结点组成的链表 A → B → C,需要反转结点中的链接成为 A ← B ← C。
今天是 LeetCode 算法的 第 1 阶段第 5 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。今天的题目是反转单链表,这道题面试被问到的几率很大,网上有些资料解释的不太清楚,我今天给你把它讲明白了。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
前提:这类问题,都不能借助其它数据结构或一些现成工具类。比如调用StringUtils.reverse(str)完成翻转,或者先入stack再出stack。仅使用最基本的分支/循环来实现最优解法。
链表反转是⼀个出现频率特别⾼的算法题,笔者过去这些年⾯试,⾄少遇到过七⼋次。其中更夸张的是曾经两天写 了三次,上午YY,下午⾦⼭云,第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个 No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题,没有之⼀。 那为什么反转这么重要呢?因为反转链表涉及结点的增加、删除等多种操作,能⾮常有效考察对指针的驾驭能⼒和 思维能⼒。 另外很多题⽬也都要⽤它来做基础, 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反 转,例如两个链表⽣成相加链表。还有⼀种是链表排序的,也是需要移动元素之间的指针,难度与此差不多。接下 来我们就具体看⼀下每个题⽬。
链表反转是一道很基础但又非常热门的算法面试题,它也在《剑指Offer》的第 24 道题出现过,至于它有多热(门)看下面的榜单就知道了。
反转单链表的迭代实现不是一个困难的事情,但是递归实现就有点难度了,如果再加一点难度,让你仅仅反转单链表中的一部分,你是否能够递归实现呢?
按照常规思维,链表反转需要知道最后一个元素,然后从最后一个元素依次往前找,直到遍历到第一个元素即完成反转。
反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬leetcode那道经典反转链表题出来,用十多张图去解析它,希望加深大家对链表反转的理解,谢谢阅读。
主要层次结构采用5层结构:应用层/传输层/网络层/数据链路层/物理层,其中部分层次中常见协议如下:
本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class RevertLink { /** * 分析:本题是要将链表“反转”,而不是反向输出,这点要特别注意。 * 反转需要改变链表的结构,使所有指针都指向相反方向; * 而反向输出不需要改变链表结构,只需反向输出即可。 * 对于反向问题可使用栈来实现,可参见我的博客《剑指offer——面试题5》,这里不再赘述。 * 下面来解决反转问题
上周周末有人和我交流反转单链表的实现代码,正好我也要写常见算法面试题系列,就着这个机会开始这个系列,和数据结构和算法系列并行,以便学以致用。
📷 1 寻找单链表中点 + 链表反转 + 链表合并 这道题是道综合题,把三个知识点串起来,非常适合复习链表处理的三个技巧 【思路】:观察发现可以把链表后一半进行反转,然后当成两个链表的合并任务即可 class Solution { public: void reorderList(ListNode* head) { if (!head) return; // 1.寻找链表中点(快慢指针) auto premid = findmid(head);
👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈 每日三题 两数相加 反转链表 回文链表 两数相加 📷 解法一 使用双指针 每次l1、l2指针都向后移动,但是可能存在一个进位然后保存下来 所以当前值每次都是(l1.val+l2.val+进位)%10,而进位值就是(l1.val+l2.val+进位 )/10 class Solution { public ListNo
binarySearch([1, 2, 10, 15, 100], 15) == 3
针对链表反转操作,我们首先可以选择采用迭代的方式进行转换,即,每当遍历两个节点的时候,我们都将next指针反转执行前置节点即可,此处需要注意的是,由于我们要修改next指针,所以,遍历的时候,我们要先将原本的next指针指向的对象进行缓存,然后再改变next指针。这么做的目的就是为了继续可以向后去执行遍历操作。具体操作方式请见下图所示:
求单链表节点中的个数 /** * 求单链表中节点的个数 * @return */ public int countNode(){ int count = 0; UserNode temp = head.next; while(true){ if(temp==null){ break; } count++;
如果将链表形式换成数组,是不是就简单很多了。针对一个长度为n的数组,我们可以一一比对节点0和节点n-1,节点1和节点n-2,直到收尾索引相等。
单链表反转这道题可谓是链表里面的高频问题了,差不多可以说只要被问到链表,就会问单链表反转。 今天我们就一起来看下。
作为一个java初学者,最近遇到了回文链表结构这个难题,经过一番学习总算搞清楚个大概。
大大小小参加过不下30+公司的面试,其中不乏BAT、TMD等一线互联网公司,总结一下,发现大厂招聘都有一个共性。
http://blog.csdn.net/zhaojinjia/article/details/12649823
链表和数组是数据类型中两个重要又常用的基础数据类型,数组是连续存储在内存中的数据结构,因此它的优势是可以通过下标迅速的找到元素的位置,而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动,为了解决和平衡此问题于是就有了链表这种数据类型。
你是否有过这种体会:看别人的代码,当时看得很明白了,但是,过段时间,自己却怎么都写不出来?这是怎么回事,可能我们也清楚。别人的思维你是无法拷贝的,形成之前不具备的思维,刻入骨髓,需要天长日久的思维训练。
在头节点的后面进行插入操作,后一个插入进来的值,在前一个插入进来的值与头节点之间。
题目 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只差一个测试用例的错
链表反转是C++面试经常会考的一道题目,下面介绍2种解法,分别是非递归法和递归法。
下图展示了单链表的基本结构: head指针是链表的头指针,指向第一个节点,每个节点的next指针域指向下一个节点,最后一个节点的next指针域为NULL,在图中用0表示。 下面先来看程序(栈的链式存储
为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像
针对如何实现单链表的逆置,提出利用头插法和递归法进行处理,通过利用IDLE编写,证明该方法是有效的,通过本次实验加深单链表基本处理操作,为更深入的有关单链表的操作积累了经验,有助于提升对单链表的操作能力。
https://leetcode-cn.com/problems/reverse-linked-list/
判断一个单链表是否为回文链表目前有两种实现思路。一种是通过数组记录前半部分与后半部分依次比较,一种是找到链表中间结点,将左半部分反转与右半部分依次比较,下面详细介绍。
https://leetcode-cn.com/problems/reorder-list/
大家好,我是熊哥。最近熊哥的一个有大厂开发经验的朋友去面试 vivo 的服务器开发工程师(C++) 岗位。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
领取专属 10元无门槛券
手把手带您无忧上云