尴尬的面试题，没有解决，估计面试官在后台偷笑

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1317 天前的主题，其中的信息可能已经有所发展或是发生改变。

给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。不删除头尾结点 typedef struct LNode{ int data; LNode *next; }LNode, *List;

函数的声明如下： void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

我没有找出解决办法一直在纠结怎么直接下标索引。结果真是想多了

lnode

结点

listnode

指针

50 条回复 • 2021-04-19 15:54:37 +08:00

zhongrs232

2021-04-17 10:27:02 +08:00

查了一下解决办法，妙啊

zxCoder

2021-04-17 10:30:49 +08:00

node.next=node.next.next 这样？

BBCCBB

2021-04-17 10:43:38 +08:00

哈哈, 搜了一下, 值替换..哈哈哈

Kangst

2021-04-17 10:47:13 +08:00 via Android

查了一下，方法是将下一个结点的值赋给当前结点，然后删除下一个结点，就相当于删除了当前节点。简直是妙蛙种子吃了妙脆角进了米奇妙妙屋，妙到家了。
node.data = node.next.data;
node.next = node.next.next;

yucao

2021-04-17 10:47:15 +08:00

把 ToBeDeleted.next 节点的内容值复制给 ToBeDeleted 节点，然后删掉 ToBeDeleted.next 节点吧...
这感觉是纯脑筋急转弯...

Cu635

2021-04-17 10:50:00 +08:00

@zxCoder
@Kangst
@yucao
那么，原先的 node->next 怎么 free ？

aijam

2021-04-17 10:51:18 +08:00

这是很基本的面试题，不会的话大厂肯定没洗

0ZXYDDu796nVCFxq

2021-04-17 10:55:22 +08:00 via Android

这种题没意义

yucao

2021-04-17 10:55:54 +08:00

@Cu635
这有何难？值复制完成后，
LNode* p = pToBeDeleted.next;
pToBeDeleted.next = pToBeDeleted.next.next;
free(p);

zxCoder

2021-04-17 10:56:15 +08:00

@Cu635

var t=node.next;
node.next=node.next.next;
free(t);

这样？

(free 啥啊让 GC 自己去 free

zxCoder

2021-04-17 10:56:36 +08:00

@zxCoder 不对写错了

constexpr

2021-04-17 11:02:27 +08:00 via Android

不遍历的话被删除的结点的父结点的指针如何设置呢？
疑惑

zhongrs232

2021-04-17 11:02:47 +08:00

想了下，这题应该是被题目坑了，如果函数参数里把头结点去掉，只留一个待删除结点作为参数，我估计大部人都能想到解法。

constexpr

2021-04-17 11:05:43 +08:00 via Android

@constexpr 如果是分配在连续空间，指针做减法倒是可以取到被删除结点的父结点

JokerZX

2021-04-17 11:23:09 +08:00

那他给头结点做啥呀

xuanbg

2021-04-17 11:25:47 +08:00

node = node.next

zhuangzhuang1988

2021-04-17 11:30:42 +08:00

"我们是专业的，再好笑都不会笑，除非忍不住"

paoqi2048

2021-04-17 11:33:34 +08:00

@JokerZX 如果待删节点为末尾节点，还是要从头节点开始遍历

nnqijiu

2021-04-17 12:45:48 +08:00

头结点就是没用的信息，算法都玩技巧了

Knuth

2021-04-17 12:49:11 +08:00 via Android

@paoqi2048 可以判断 node. next，不用遍历

Rocketer

2021-04-17 12:53:52 +08:00 via iPhone

好像在《数学之美》里见过，但从来没用到过，因为 leetcode 里类似的题都要求不能改 node 的值

eephee

2021-04-17 13:10:20 +08:00 via Android

@Knuth 不用遍历怎么删除呢？

FACEB00K

2021-04-17 13:22:06 +08:00

昨天在 leetcode 上做过，评论还是挺搞笑的 https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

wheeler

2021-04-17 13:36:03 +08:00 via iPhone

《剑指 offer 》的 13 题。

yolee599

2021-04-17 13:48:27 +08:00 via Android

@eephee 无需知道前驱节点，直接把要删除的节点替换为下一个节点。next 变成下一个节点的 next，data 变成下一个节点的 data

smdbh

2021-04-17 14:18:58 +08:00

我想知道原来指向下一个节点的指针，怎么办？

zmxnv123

2021-04-17 14:30:04 +08:00 via iPhone

剑指 offer 至少 dei 刷几遍吧

xinshoushanglu

2021-04-17 15:30:23 +08:00

可以，脑筋急转弯哈哈

raaaaaar

2021-04-17 15:44:34 +08:00

表示我们数据结构课上就讲了。。

felixlong

2021-04-17 16:34:45 +08:00

nngt 。这是脑筋急转弯啊。这不是删除，这是交换。

securityCoding

2021-04-17 17:14:04 +08:00

面了三家大厂,算法题全部是中等题 , 回溯+动态规划

Edcwsyh

2021-04-17 17:17:22 +08:00

@felixlong 这没用交换, 就是单纯的移动覆盖...

Knuth

2021-04-17 18:14:05 +08:00 via Android

@eephee node. next 为空，直接把当前节点置空不就是删除了

Kangst

2021-04-17 19:56:03 +08:00

@Cu635 针对这道题而言，用 c/c++好像不能 free，可以参考 leetcode 237 题里面 c++的一个题解，讨论了这个问题。
另外，力扣官网的剑指 Offer 18 也是这个题，题目说明里写了如果使用 c/c++不需要考虑 delete 或 free 结点；我觉得这题就当个脑筋急转弯，能得到结果就行了，本身题目就不好。