在恒定时间内将节点插入链表？

Question

我正在做一个作业，告诉我假设我有一个带有标题和尾部节点的单链接列表。它要我在位置p之前插入项目y。有人可以查看我的代码并告诉我我是否走对了吗？如果没有，您能为我提供任何提示或指示（无双关语）吗？

tmp = new Node();
tmp.element = p.element;
tmp.next = p.next;
p.element = y;
p.next = tmp;

我认为我可能是错的，因为即使在问题描述中特别提到了头和尾节点，我也根本不使用头和尾节点。我正在考虑编写一个while循环来遍历列表，直到找到p并以这种方式解决问题，但这不是固定时间的，对吗？

Answer 1

如果遇到问题，只需写下来即可：

// First we have a pointer to a node containing element (elm) 
// with possible a next element.
// Graphically drawn as:
// p -> [elm] -> ???

tmp = new Node();
// A new node is created. Variable tmp points to the new node which 
// currently has no value.
// p   -> [elm] -> ???
// tmp -> [?]

tmp.element = p.element;

// The new node now has the same element as the original.
// p   -> [elm] -> ???
// tmp -> [elm]

tmp.next = p.next;

// The new node now has the same next node as the original.
// p   -> [elm] -> ???
// tmp -> [elm] -> ???

p.element = y;

// The original node now contains the element y.
// p   -> [y] -> ???
// tmp -> [elm] -> ???

p.next = tmp;

// The new node is now the next node from the following.
// p   -> [y] -> [elm] -> ???
// tmp -> [elm] -> ???

您已达到要求的效果，但是它可以提高效率，我敢打赌，您现在就可以了解自己。

写这样的东西更清晰：

tmp = new Node();
tmp.element = y;
tmp.next = p;
p = tmp;

如果p不可变，那当然不起作用。但是，如果p == NULL，则您的算法将失败。

但是我要说的是，如果您对算法有疑问，只需写下效果即可。尤其是对于树和链表，您需要确保所有指针都指向严格的方向，否则会造成混乱。