您的位置: 题酷首页 » 所有题目 » 面试题之链表问题 - 删除环状单链表的一个节点


面试题之链表问题 - 删除环状单链表的一个节点


0
0
1 答
583 看

给定一个链表,比如:

struct Node {
  Node *next;
  int data;
};

条件

  1. 这是一个环状单链表(整个就是一个环)
  2. 知道一个指向某节点的指针Node *p
  3. 我们想要删除这个节点p
  4. 链表很长,遍历一遍很慢的

怎么办?

作业题链表
2009/08/25 by 半瓶墨水 6个月前更新 更新记录



0

这个问题挺有趣的,类似现实中的问题,只需要一个有效率的解决办法就行了。比如说假设指针和int相同大小,我们不直接删除节点p,而是做下标记:让p->data指向p->next(因为p->data不需要了嘛),而让p->next指向它的父节点,下回某个遍历走到p的时候,发现p->next与自己相等就会意识到p是需要删除的节点。这个方法需要记录环的长度适应一个或两个节点时的情况。

1 呵呵,不错,现实中有很多解决方案;我觉得直接让p.data=p->next->data;p->next=p->next->next;然后删掉p->next比较直接半瓶墨水, 6个月前

250x

参与回答

 提示:如不是回答问题,请采用发表评论形式! (比如针对题目或者某个回复的意见、建议)

注册登录后再回答