关于一道考研题算法的实现

Question

题目描述

一个整数队列中有 n 个元素，请问：是否存在与 n 无关的方法，来删除这个队列中的一个特
定的元素。如果可能，请给出你的数据结构和删除算法，算法用函数表示，函数的定义如下；如
果不可能，请说明你的理由。
函数定义：

void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
{
    // 加入你的代码，如果你认为这样的方法存在的话
}

题目来源及自己的思路

浙江理工的考研题，自己感觉根本不可能存在这样的算法。但是这样那一道大题岂不是根本不用做了？

Answer 1

ListNode 的定义给你了么，不给你怎么写。

---

这题不会是让你自己去定义 ListNode 的结构吧，那果断双向链表啊，可以完美达到O(1)的复杂度，如果只用单向链表的话，复杂度就是O(n)，因为你要遍历找到删除节点的前一个节点。

Answer 2

只要被删除的节点上记录了前后节点的指针（这就是你的数据结构），那时间复杂度就跟n无关。

Answer 3

我觉得与n无关是一句废话.他的意思就是说
给你一个起点,和一个节点,在链表上删除这个节点.

只需要循环,当current.next == *target的时候,将current.next指向target.next就完了.
如果是双向链表,那连起点都可以不要了.

Answer 4

双向链表了解一下