链表从某些位置混乱中删除节点

Question

假设我们有这个链表：a-> s-> d -> f，我们想删除 d。

我无法理解为什么下面的代码可以正确地从链接列表中删除一个项目，为什么下面的代码不会产生相同的结果？

正确代码：

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
 }

错误代码：

 public void deleteNode(ListNode node) {
        node = node.next;//d now points to f
        //So wouldn't node s.next now equal f 
        //because we have changed what node d references to? 
 }

谢谢！

Answer 1

要意识到的重要一点是，第一个代码实际上并没有 "delete the Node 'd'"（就像名字所暗示的那样），而是删除了 value d.

它通过将值从下一个节点（在您的示例中为 "f"）复制到当前节点（先前包含 "d" 的节点）然后删除下一个节点（节点包含 "f")，这不再是必需的，因为我们在当前节点中有一个值的副本。

a -> s -> d -> f
a -> s -> f -> f
a -> s -> f

我觉得有点混乱，我个人会直接删除节点"d"，而不移动任何内容。我想，这样做是为了更好地分离节点搜索和删除。如果你真的想删除某个 node（不是它的内容），你需要引用它的 previous 节点。这可能会使界面复杂化。

第二个代码正是因为那个问题而失败。它试图删除给定的节点 - 但它不能，因为删除它意味着更新前一个节点的 .next 成员，我们无权访问它。错误代码中的语句只是更改了 local 变量中的引用，这对实际列表没有任何影响。

链表从某些位置混乱中删除节点

Linked List removing a node from certain position confusion

java

linked-list

data-structures