图解 Google 笔试:删除链表结点(挺难的)

飞天小牛肉

共 1125字,需浏览 3分钟

 ·

2021-09-30 12:07

大家好,我是道哥。今天,我们来看一道谷歌笔试的题目。原题是英文陈述的,翻译过来后如下:
有一个足够长的单链表,并且头指针未知。靠近中间位置附近有一个结点,指针是p,请把该结点删除。
单链表删除结点何其容易啊,但是,谷歌会出这么简单的题目吗?可别忘了题目的限制:不知道头指针。

一. 单链表删除操作

首先,得搞清楚什么是单链表,这个问题很简单啊,来看看动图就明白了,这些水果都是我爱吃的。
这些水果,你应该都认识吧:西瓜🍉,苹果🍎,梨🍐,橙子🍊,香蕉🍌,我天天买,也挺耗费钱的。

单链表的动图


接下来,我们看看什么叫删除当前结点,比如,我们要把梨子🍐从单链表中删除,动图如下:

单链表结点删除的动图


很显然,要删除梨子🍐,就得把前面的苹果🍎和后面的橙子🍊连接上,这样才能形成删除后的链表。

可是,现在的问题是:不知道单链表的头指针,所以也就没法知道苹果🍎的指针,所以看来要歇菜了。

貌似无解,当时笔试时,我也曾自言自语,这不是在戏弄我吗?于是我写下了:Impossile(不可能)。


二. 摆脱僵化的思维

我当然也知道,谷歌不会那么无聊,还是来看看题目的解法吧。原始的单链表如下,待删除的结点为p:

再看仍是没有思路啊。没关系,我们来看看删除后的预想结果:


总之,目的就是要留下:100, 200, 300, 400.  那么可以这样去考虑,先把p结点的值改一下:

p->data = p->next->data;


然后考虑把p后面的结点删除就行,这很容易吧!操作步骤和结果如下:
q = p->next;
p->next = p->next->next;

free(q);

这样就达到目的了,看似不可能的事情,结果又可能了。谷歌、微软之类的公司,就喜欢问类似的问题。


跳出思维的局限很重要,要拥有创造性思维,也就是我们常说的:Think outside the box. 顺便来回顾一下当时的思维局限,以为是一定要删除梨子🍐这个结点呢:


这篇文章并不难,关键还是在于思路。我们也会一步一个脚印,争取每篇文章讲清讲透一件事,也希望大家阅读后有所收获,心情愉快。

你好,我是道哥,CSDN前30名,曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。欢迎点击如下名片关注道哥,感谢点赞和在看支持哦。

朋友,点个“赞”和“在看”鼓励下呗

浏览 38
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报