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

V2EX = way to explore

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

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 1845 days ago, the information mentioned may be changed or developed.

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

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

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

lnode

结点

listnode

指针

50 replies • 2021-04-19 15:54:37 +08:00

zhongrs232

Apr 17, 2021

查了一下解决办法，妙啊

zxCoder

Apr 17, 2021

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

BBCCBB

Apr 17, 2021

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

Kangst

Apr 17, 2021 via Android

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

yucao

Apr 17, 2021

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

Cu635

Apr 17, 2021

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

aijam

Apr 17, 2021

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

0ZXYDDu796nVCFxq

Apr 17, 2021 via Android

这种题没意义

yucao

Apr 17, 2021

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

zxCoder

Apr 17, 2021

@Cu635

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

这样？

(free 啥啊让 GC 自己去 free

zxCoder

Apr 17, 2021

@zxCoder 不对写错了

constexpr

Apr 17, 2021 via Android

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

zhongrs232

Apr 17, 2021

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

constexpr

Apr 17, 2021 via Android

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

JokerZX

Apr 17, 2021

那他给头结点做啥呀

xuanbg

Apr 17, 2021

node = node.next

zhuangzhuang1988

Apr 17, 2021

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

paoqi2048

Apr 17, 2021

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

nnqijiu

Apr 17, 2021

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

Knuth

Apr 17, 2021 via Android

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

Rocketer

Apr 17, 2021 via iPhone

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

eephee

Apr 17, 2021 via Android

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

FACEB00K

Apr 17, 2021

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

wheeler

Apr 17, 2021 via iPhone

《剑指 offer 》的 13 题。

yolee599

Apr 17, 2021 via Android

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

smdbh

Apr 17, 2021

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

xe2vherd

Apr 17, 2021 via iPhone

剑指 offer 至少 dei 刷几遍吧

xinshoushanglu

Apr 17, 2021

可以，脑筋急转弯哈哈

raaaaaar

Apr 17, 2021

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

felixlong

Apr 17, 2021

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

securityCoding

Apr 17, 2021

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

Crimson47

Apr 17, 2021

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

Knuth

Apr 17, 2021 via Android

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

Kangst

Apr 17, 2021

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