1

我从一本书的链接列表中遇到了一个问题，但我无法理解它想说什么？

是不是：1. finding middle element but looking from starting。这些行是什么意思：

n is c????

LinkedListNode next = n.next;   // next= d;
6 n.data = next.data;  // n.data=d;
7 n.next = next.next; // c.next= e ???

我无法得到它，你能看看并告诉我吗？

实现一个算法来删除单个链表中间的一个节点，只允许访问该节点。

示例：
输入：链表 a->b->c->d->e 中的节点 'c'
结果：没有返回任何内容，但新的链表看起来像 a->b->d->e

解决方案：
只需将下一个节点的数据复制到这个节点中，然后删除下一个节点即可。
注意：如果要删除的节点是链表中的最后一个节点，则无法解决此问题。没关系——你的面试官希望看到你指出这一点。在这种情况下，您可以考虑将其标记为 dummy。这是你应该与面试官讨论的问题。

1 public static boolean deleteNode(LinkedListNode n) {
2   if (n == null || n.next == null) {
3     return false; // Failure
4   }
5   LinkedListNode next = n.next;
6   n.data = next.data;
7   n.next = next.next;
8   return true;
9 }

在这里，可能是n什么？你能解释一下第 5,6,7 行吗？n另外，如果是最后一个元素，为什么它不起作用？

我是链表的新手。我正在阅读它的所有示例，但真的被困在这个例子上。

4

2 回答 2

1

该问题要求您从链表中间删除一个节点，仅给出对要删除的节点的引用。

在这里，n 可能是什么？

n 可以是对链表中任何“中间”节点的引用，即，不是第一个或最后一个节点。

你能解释一下第 5,6,7 行吗？

问题是，由于列表不是双向链接的，因此您无法在不破坏链接列表的情况下删除给您的节点（前一个节点将指向 null ）。

例如，如果我们要删除 c，b 会指向哪里？

a->b->c->d->e

a->b-> d->e

由于我们不知道 c 之前是哪个节点，所以我们无法再次链接列表。所以解决方法是将d中的值复制到节点c中，然后删除节点d。然后列表没有损坏，并且您已从中删除了一个节点。那么旧的节点 c 将实际代表 d 节点，它将在节点 e 处继续链表。

a->b->c->d->e

a->b->d->e

这些行只是从节点 d 复制数据并将其存储在节点 c 中，以便随后可以删除节点 d。

如果 n 是最后一个元素，为什么它不起作用？

如果 n 是最后一个元素，则列表中的下一个节点为空，因此我们没有可以复制到当前节点的任何内容。

于 2013-07-10T14:54:50.363 回答
0

您指出的行正在执行以下操作：

n.data = next.data;

从下一个节点复制数据；

n.next = next.next;

更改“now”节点的下一个链接；现在当前节点是“下一个”节点的相同副本，并且无法从列表的头部到达下一个节点。

换句话说，这个算法实际上并没有删除当前节点——它把数据从下一个节点复制到当前节点，并从链接链中删除下一个节点，因此当前节点上的数据丢失，当前节点作为下一个节点，下一个节点被有效删除。

如果当前节点是最后一个节点，则 next.data 将抛出 NullPointerException。

于 2013-07-10T14:53:50.203 回答