1

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

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

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

4

7 回答 7

5

如果您遇到算法困难，只需将其写下来：

// 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，您的算法将失败。

但我想说的是，如果你对算法有问题，就把效果写出来。特别是对于树和链表，你需要确保所有的指针都指向正确的方向，否则你会弄得一团糟。

于 2008-11-16T19:10:54.227 回答
4

提示：仅当位置n = 0 或链表的头部时，插入链表才是常数。否则，最坏情况的复杂度为O(n)。这并不是说您不能创建一个相当有效的算法，但它总是至少具有线性复杂性。

于 2008-11-16T19:15:21.473 回答
1

问题中给出头部和尾部节点的原因是如果您创建的替换节点恰好成为头部或尾部，则更新头部和尾部引用。换句话说，给定的前一个节点要么是头部，要么是尾部。

于 2010-07-17T23:53:48.260 回答
0

您没有做的是在将 y 插入到 y 之前将 p 之前的元素链接起来。因此，虽然 y 在 p 之前插入，但现在没有人指向 y（至少不在您显示的代码中）。

如果您知道必须插入 y 的元素的位置，则只能在恒定时间内插入。如果您必须搜索该位置，那么您永远无法在单个链接列表中进行恒定时间插入。

于 2008-11-16T19:25:03.870 回答
0

使用已经存在的代码怎么样？LinkedHashMap、LinkedList、LinkedHashSet。您还可以查看代码并从中学习。

于 2008-11-17T04:17:22.423 回答
0 
create a node ptr
ptr->info = item //item is the element to be inserted...
ptr->next = NULL
if (start == NULL) //insertion at the end...
    start = ptr
else
    temp = ptr
    while (temp->next != NULL)
        temp = temp->next
    end while 
end if
if (start == NULL) //insertion at the beginning...
    start = ptr
else
    temp = start
    ptr->info = item
    ptr->next = start
    start = ptr
end if
temp = start //insertion at specified location...
for (i = 1; i < pos-1; i++)
    if (start == NULL)
        start = ptr
    else
        t = temp
        temp = temp->next
    end if
end for
t->next = ptr->next
t->next = ptr
于 2010-03-31T17:09:36.237 回答
0

在一个单独的 LinkedList 中，仅将一个节点添加到列表的开头或创建一个只有一个节点的列表将花费 O(1)。或者因为他们已经提供了 TailNode，所以在列表末尾插入节点需要 O(1)。

每隔一个插入操作将花费 O(n)。

于 2012-12-11T18:58:36.173 回答