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

我正在进行一项任务,告诉我假设我有一个带有标题和尾节点的单链表.它要我在位置p之前插入一个项目y.任何人都可以查看我的代码并告诉我,我是否在正确的轨道上？如果没有,你可以向我提供任何提示或指示(没有双关语)？

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

我想我可能是错的,因为我根本没有使用头部和尾部节点,即使在问题描述中特别提到它们.我正在考虑编写一个while循环来遍历列表,直到它找到p并解决问题,但这不会是恒定时间,是吗？

如果你遇到一个算法,就把它写下来:

// 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,则算法会失败.

但我想说的是,如果你有一个算法问题,只需写出效果.特别是对于树木和链接列表,你需要确保所有指针指向正方向,否则你会变得很乱.