上周周末有人和我交流反转单链表的实现代码,正好我也要写常见算法面试题系列,就着这个机会开始这个系列,和数据结构和算法系列并行,以便学以致用。
反转单链表的迭代实现不是一个困难的事情,但是递归实现就有点难度了,如果再加一点难度,让你仅仅反转单链表中的一部分,你是否能够递归实现呢?
定义函数使三个变量迭代,确定指向,也可以使用比如循环或者递归之类的方法反转单链表。
这种递归的思路非常巧妙,通过不断地递归调用自身,将问题分解成规模更小的子问题,并最终将这些子问题的解合并起来得到原问题的解。在代码实现时,确实需要考虑如何处理 base case,即当剩余的节点不足 k 个时的情况。
可以看到,一个链表的节点包含数据域和指向下一个节点的引用,链表最后一个节点指向null(空区域)。
若要满足 O(1) 空间复杂度,则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问,所以这里采用的方式为,找到单链表中间元素,并反转单链表前半部分,然后与单链表后半部分进行比较是否为回文结构。
当搜索一个键时,哈希表使用相同的哈希函数来查找对应的桶,并只在特定的桶中进行搜索。
本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class RevertLink { /** * 分析:本题是要将链表“反转”,而不是反向输出,这点要特别注意。 * 反转需要改变链表的结构,使所有指针都指向相反方向; * 而反向输出不需要改变链表结构,只需反向输出即可。 * 对于反向问题可使用栈来实现,可参见我的博客《剑指offer——面试题5》,这里不再赘述。 * 下面来解决反转问题
1 反转单链表 解题思路 使用两个临时变量,分别标记反转过程中的两个链表的头。 class Solution { public ListNode reverseList(ListNode he
今天是 LeetCode 算法的 第 1 阶段第 5 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。今天的题目是反转单链表,这道题面试被问到的几率很大,网上有些资料解释的不太清楚,我今天给你把它讲明白了。
以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。
LeetCode 是著名的练习数据结构与算法的网站,很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时,该网站的很多数据结构及算法题都是面试中的真题。
对于是否带头的判断依据,几乎所有的结论都聚焦在“操作区别”上,但是其实是否带头涉及到一个内存泄露的问题。
class ListNode { public int data; public ListNode next; public ListNode(int data){ this.data = data; this.next = null; } } public class TestDemo1024_1 { public ListNode head; //反转单链表 public ListNode change(){
前几天有个朋友去面试,面试官问了他一道链表相关的算法题,不过他一时之间没做出来,就来问了我一下,感觉这道题还不错,拿来讲一讲。
大家好,我是来自华为的「程序员小熊」。相信绝大部分童鞋都知道,在处理与「链表」相关问题时,常用的解题套路主要包括「双指针」、「迭代」和「虚拟头节点」等等。
今天是 LeetCode 算法的 第 1 阶段第 4 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。
版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。
为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像
这里我们使用创建一个变量cur来遍历原链表,再创建一个新节点newnode,首先使用一个循环来遍历原链表,cur为NULL是循环结束,每次进入循环将cur的下一个节点赋给tail,然后将cur取下来头插,第一次头插的节点的next置为NULL,也就是cur->next=newnode,然后将cur这个节点赋给newnode,在新链表上相当于往左走一步,newnode=cur,然后cur在旧链表上往右走,cur=tail。循环结束后cur就为NULL了,也就是全部完成头插了,这是newnode也走到了新链表最左边的位置,也就是成为了头节点,这时返回newnode就行了。
经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个指针的距离保持在k-1,当第一个指针到达链表的尾节点时,第二个指针刚好指向倒数第k个节点。
可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!
链表是一个「线性」结构,充分利用了计算机的内存空间,实现了灵活的内存状态管理。在物理存储结构上,链表是不连续、无顺序的存储结构,在逻辑上,通过使用节点的引用实现顺序。
Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively.
9、一个文本文件中每行有一个手机号或电话号,给定一个手机号,判断该文件中是否存在。给出时间复杂度较低的方案。
/** * 单链表 */ class Node{ public int data; public Node next; public Node(int data){ this.data = data; this.next = null; } } public class MyLinkedList { public Node head;//保存头节点的引用 // 1、无头单向非循环链表实现-----------------
在Google.com.hk或者在Google.com上搜索 递归或者recursion 发现Google“抽了”,明明搜索正确,为啥还显示一个查询错误的提示?如下两图:
第二,程序员面试必考察数据结构与算法,尤其是大厂,因为算法和数据结构最能体现一个人的基本功,基本功扎实的人,无论是做工程还是去做算法,都不会差到哪里去。
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
版权所有,转载请注明出处,谢谢! http://blog.csdn.net/walkinginthewind/article/details/7393134
数据结构和算法 链表 链表,常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分,这个一般必须得完全无误的情况下写出来; 给出两个链表的头结点,找出这两个链表的交点。 java 中数组和链表的区别,各自优势 如何设计拥有高效的随机读取能力的的链表(跳表) 设计跳表,跳表插入开销,跳表随机读取过程 给你一个单向链表,给这个链表做K反转,例如 k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 反转后为:3 -> 2 -> 1 -> 6 -> 5 -> 4 链表长度保证为K的
这份面试资源主要包含五部分内容:数组、链表、字符串、二叉树和重要算法(如排序算法)的编程面试题,其中每部分内容我们都列出了一些最常被问到的热门问题,并且在每个题目后给出了可以参考的解决思路和代码,因为题目较多,我们没有罗列所有的方法和代码,只给出了访问地址。相信大家在掌握了这些内容后,一定可以提升实力、信心大增。
进入面试流程的包括字节跳动、招银科技、百度、Keep、华为、花旗、京东、有赞、去哪儿、拼多多、okcoin,收到的offer有华为、招银、有赞、去哪儿,其他有一面凉、二面凉以及HR面凉等等。
眨眼间,2021年就快过去了,这两年,我们经历了新冠疫情的洗礼,导致今年的互联网环境太差,很多程序员都经历了失业,找工作的恐慌,所以我们更加需要自己有足够的知识储备,才能够应对这凌冽的寒风。
笔者非科班转行,两个月拿了十多个offer,其中包括了互联网大厂,央企,国企,银行等,下面看看都面了什么(部分回忆)。总之,在面试国企等企业时,会有一些有意思的问题,也会出现群面的场景。 1 阿里一面 指针和引用的区别 define和const 内联函数和define c++内存管理 栈和堆区别,全局变量和局部变量 c++多态,虚函数,纯虚函数 多态的好处 数据库索引,给一个语句问有没有用到索引,底层怎么实现的 B树和B+树 哈希冲突 说一说常见的排序算法和时间,空间复杂度 TCP,UDP,可靠传输,网络什
今天签了三方,终于结束了我的秋招之旅。秋招拿到了一些offer,也算是蛮有收获的。想写一点东西来回馈大家。 首先是关于实习,大家在找实习的时候尽量找个互联网的实习,这样秋招至少会顺利一半吧,而且互联网的实习是基本可以留用的,秋招时手里有个offer心里就不是很慌了。不过如果想去券商工作的话,实习的时候找个券商实习还是不错的,无论留用与否,在参加券商的秋招时会非常有优势的,说句题外话,券商的实习留用率不是很高,而且有些偏爱男生。 因为实习,手里有个互联网的offer,但是因为不太喜欢里面的工作氛围,还有一些个
本期例题:LeetCode 206 - Reverse Linked List[1](Easy)
领取专属 10元无门槛券
手把手带您无忧上云