我在一本书的链表中遇到了一个问题,但我不明白它想说什么?
是: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解决方案:
只需将数据从下一个节点复制到此节点,然后删除下一个结点
注意:如果要删除的节点是链表中的最后一个节点,则无法解决此问题。没关系——你的面试官希望看到你指出这一点。在这种情况下,您可以考虑将其标记为虚设。这是一个你应该和面试官讨论的问题。
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
是最后一个元素,为什么它不起作用?
我是链接列表的新手。我正在阅读所有的例子,但我真的被这一个卡住了。
该问题要求您从链表中间删除一个节点,只给定要删除的节点的引用。
在这里,n可能是什么?
n可以是对链表中任何"中间"节点的引用,即不是第一个或最后一个节点。
你能解释第5,6,7行吗?
问题是,由于列表不是双重链接的,您无法在不破坏链接列表的情况下删除给定的节点(上一个节点将指向null)。
例如,如果我们删除c,b会指向哪里?
a->b->c->d->e
a->b-> nbsp;d->e
由于我们不知道c之前的节点是什么,所以我们没有办法再次链接列表。因此,解决方案是将d的值复制到节点c中,然后删除节点d。然后列表没有被破坏,你已经从中删除了一个节点。然后,旧的节点c将实际代表d节点,它将在节点e继续链表。
a->b->c->d->e
a->b->d->e
这些行只是从节点d复制数据并将其存储在节点c中,这样就可以删除节点d。
如果n是最后一个元素,为什么它不起作用?
如果n是最后一个元素,则列表中的下一个节点为null,因此我们没有可以复制到当前节点的内容。
您指出的行正在执行以下操作:
n.data = next.data;
从下一个节点复制数据;
n.next = next.next;
更改"现在"节点的下一个链接;现在,当前节点是"下一个"节点的相同副本,并且无法从列表的开头访问下一个节点。
换句话说,这种算法实际上并没有删除当前节点——它将数据从下一个节点复制到当前节点,并将下一个结点从链接链中删除,从而丢失了当前节点上的数据,并且当前节点充当下一个节点,有效地删除了下一节点。
如果当前节点是最后一个节点,那么next.data将抛出NullPointerException。