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

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，你的算法就会失败。

但我的意思是，如果您对算法有疑问，只需写出效果即可。尤其是对于树和链表，你需要确保所有指针都指向正确的方向，否则你会搞得一团糟。