面试中必知必会的那些题——第一题 单链表倒置
我想你去很多家公司面试的时候,遇到单链表倒置的问题可能比较多,如果一定要给面试题来一个排名,估计也能上top10吧,其实这个
题目玩的是技巧和你对单链表的理解,其实我们仔细想想也不是很难,既然是倒置,那我们一定是一定要走一遍单链表的,对吧,那么走单链
表有两种形式,递归和循环两种方式,而递归正是压栈和出栈,那么我们就想起来了,这不就是顺序和逆序的关系吗?第二种就是循环,还记
得我们曾今学习单链表的时候有一种插法叫做头插法,这种插入复杂度为O(1),不好的地方就是顺序插入的数字,出来的时候却是反的,所以这
个不就是可以将原先的链表原地倒置过来吗?
一:递归
说到递归,我们脑子里面一定要有一个V型图,还有一个就是好记性不如烂笔头,算法这东西很难用脑子想的清楚的,多画画图就见青天了,
下面我就举个简单的例子:现有链表L={8,1,6,3},需要将L倒置,然后我就画好了V型图。
从图中可以看到,当我递归到3再出栈的时候,只需要将6赋给3.next,1赋给6.next,然后这样以此类推。。。最后结果就出来了,貌似
口头上描述起来很简单,但是在写代码的时候需要注意以下几个点,先上代码说话。
1 public LinkNode Reverse(LinkNode node) 2 { 3 if (node.next == null) 4 return node; 5 6 var prevNode = Reverse(node.next); 7 8 var temp = node.next; 9 10 temp.next = node; 11 12 node.next = null; 13 14 return prevNode; 15 }
第一点:我们在走链表的时候,可以操控的只有两个结点,node和node.next,所以递归出口的时候,一定不能使用最常见的写法。
1 if (node == null) 2 return node;
而应该像下面这么写,其实就告诉我们只需要走到6节点就行了,用6.next来判断下是不是链尾,这样做是方便我们进行node和
node.next进行节点交换。
1 if (node.next == null) 2 return node;
第二点:当我们每一次出栈的时候,其实也是退到曾今压栈时的方法环境中,进行节点交换的时候,也只能在当前的方法上下文中起效,比如
说:出栈到1的时候,其实3和6的节点已经交换了,但是1这个方法环境不知道,它仍然指向6,但此时节点6.next再也不是3了,因为
曾今3和6进行了交换,所以这不是我们所期望的,所以在回退的时候,一定要有一个链表保存这个所有节点交换的集合,恰巧在链表中
有一个特征就是,只要我有一个指针始终指向头结点的地址,它就相当于一个集合的功能了,因为我不管你后面节点怎么转换,我都可以
通过head.next依次找到后面痉挛的所有结点,比如下图中在出栈的过程中,每个出栈的方法环境中都依次交换了node和node.next结
点,而我的prevnode始终指向的是结点3,所以我通过3.next就可以找到后面所有的 变化,所以这里就是prevnode的精妙之处。
最后看一下倒置的输出结果:
二:非递归实现
如果你知道头插法,那么循环实现真的很简单,不像递归做法很难想到那个prevnode节点,我们知道头插法是把新节点插入到链表的头部,
而我们遍历的时候又可以控制两个节点node和node.next,所以依次采用头插法,将node.next插入到node之前,有人说,那插入到node节
点之前不就乱了吗?所以在操作之前,我可以把node.next先保存起来,比如放到申请的一个叫next的节点上,为了保存新转换的节点,我们再
申请一个prev结点来保存头插法中的新节点。
为了好理解,画图如下,其实这里要注意,结点还是那些结点,并没有删除再添加。
1 public LinkNode Reserve(LinkNode node) 2 { 3 LinkNode prev = null; 4 LinkNode next = null; 5 6 while (node != null) 7 { 8 next = node.next; 9 10 node.next = prev; 11 12 prev = node; 13 14 node = next; 15 } 16 return prev; 17 }
其实我们发现,代码只有那么一点点,但是信息量还是蛮大的,这些东西要是用口头描述还是很累的。
相关文章
- [Go] 获取文件夹下面指定模式的文件列表 , 并且获取文件创建时间删除超过30分钟的文件
- [javascript] elementui下login登录页界面和js验证逻辑
- [linux]centos安装宝塔面板
- [javascript] vuejs的elementui配合iframe实现页面跳转
- [Go] 使用字面值方式初始化map
- [javascript] 基于elementui的后台界面开发
- [linux] linux宝塔面板安装GOFLY开源客服
- [docker] win10 docker桌面版镜像源
- [docker]解决:docker桌面版报错error during connect: This error may indicate that the docker daemon is not running
- [MySQL] 索引优化不只是用于面试
- [正则]正则表达式里面的?: ?! ?= ?<=
- 万字解读鸿蒙轻内核物理内存模块
- 上万规模数据湖如何在实验室测试
- 测试用例又双叒叕失败了,NLP帮你
- 云小课|大数据时代的隐私利器-GaussDB(DWS)数据脱敏
- ReplacingMergeTree:实现Clickhouse数据更新
- 华为云·核心伙伴开发者训练营——产业云专场在东莞松山湖圆满落幕
- 超全整理:程序员都在用什么工具?
- 顶会VLDB‘22论文解读:CAE-ENSEMBLE算法
- 拥抱时序数据库,构筑IoT时代下智慧康养数据存储底座