Google笔试：删除链表结点(挺难的)

作者丨道哥

来源丨爱码有道（ID：aimayoudao）

大家好，我是道哥。今天，我们来看一道谷歌笔试的题目。原题是英文陈述的，翻译过来后如下：有一个足够长的单链表，并且头指针未知。靠近中间位置附近有一个结点，指针是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等多方面的编程知识。

点分享

点点赞

点在看