链表训练2:删除单链表的中间节点
【题目描述】
给定链表的头节点head,实现删除链表的中间节点的函数。
例如:
步删除任何节点;
1->2,删除节点1;
1->2->3,删除节点2;
1->2->3->4,删除节点2;
1->2->3->4-5,删除节点3;
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)
【解答】
这道题要求删除中间节点,我们可以采用双指针的方法来做,就是用一个快指针和一个慢指针,快指针每次前进两个节点,而慢指针每次前进一个节点。当快指针遍历完节点时,慢指针刚好就在中间节点了。
不过在做的时候,最好是先把一些特殊情况先处理好,例如删除的可能是第一个节点,也有可能不用删除节点(只有一个节点时就不用删除了。
代码如下
上次那道删除倒数第 K 个节点的题其实也是可以使用双指针的,但个人认为,那道题使用双指针的方法并没有我上次那个做法优雅,而这次删除中间节点,则用双指针比较优雅。至于原因,可以自己打下代码看看
问题拓展
题目:删除链表中 a / b 处的节点
【题目描述】
给定链表的头节点 head、整数 a 和 b,实现删除位于 a/b 处节点的函数。
例如:
链表:1->2->3->4->5,假设 a/b 的值为 r。
如果 r = 0,不删除任何节点;
如果 r 在区间 (0,1/5] 上,删除节点 1;
如果 r 在区间 (1/5,2/5] 上,删除节点 2;
如果 r 在区间 (2/5,3/5] 上,删除节点 3;
如果 r 在区间 (3/5,4/5] 上,删除节点 4;
如果 r 在区间 (4/5,1] 上,删除节点 5;
如果 r 大于 1,不删除任何节点。
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)
【解答】
可以自己动手做一下或者想一下,下面我直接给出答案了,答案有详细的解释
对于上面的那道题,面试被问过 n 遍,大家一定要用快慢指针来处理,这样不容易出错,也有人觉得可以先统计一下节点的个数,然后再来删除第 n/2 个节点,其实方法其实也是可以的,并复杂度一样,不过个人感觉快慢指针这种方法比较高逼格,并且不容易出错。
对于拓展题,大家也可以做一做,不过比较少考到
对了,如果你能提供其他代码版本,欢迎评论区给出哈。
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人,帅地正在疯狂更新中….