为什么一个方法会破坏我的链表而另一个不会？

Question

我看到类似的问题被问过，但是没有一个答案真正解决了我的困惑。

我正在学习链表相关的内容，尝试编写解决类似leetcode问题的方法。我正在使用单向链表，定义为：

public class LinkedListy {
ListNode head;
LinkedListy(){};

   public static class ListNode { 
      int val; //integer variable
      ListNode next; //pointer

      ListNode() {} 

      ListNode(int val) { 
          this.val = val; 
      }

      ListNode(int val, ListNode next) { 
          this.val = val; this.next = next; 
      }
  }
  ...

我正在尝试编写一个函数来反转我的链表，但不会破坏原始链表。我编写的代码可以反转链表，但会破坏原始链表。

public ListNode reverse() {
    //use copyList function to avoid altering head --> DOESN'T WORK
    ListNode current = head;
    ListNode temp = null;
    ListNode copied_result = null;

    while(current != null){
        temp = current.next;
        current.next = copied_result;
        copied_result = current;
        current = temp;
    }
    return copied_result;
}

从本网站和其他地方的阅读中，我了解到通过将current = head，我只是为同一个ListNode创建一个新引用。因此，当我运行我的代码时，我会改变原始列表。

主要困惑：我感到困惑的是，我编写的方法并没有破坏原始列表，但使用了与head相同类型的引用。例如，在我的“length（）”方法中，我设置dummy = head并更改dummy以查找列表的长度。 但是，然后原始列表并没有被更改（我编写了一个打印函数来打印列表，我验证它在调用length（）之前和之后打印相同的内容）。

    public int length() {
    ListNode dummy = head;
    int length = 0;
    while(dummy != null) {
        dummy = dummy.next;
        length++;
    }
    return length;
}

显然我对链表的某些基本问题理解不透彻。

1. 为什么我的reverse()方法会破坏原始链表，而我的length()方法却不会？
2. 写一个反转链表的方法，除了在主方法中复制原始链表并反转副本之外，还有没有其他方法可以不破坏原始链表？

非常感谢任何帮助或资源。谢谢！

- Laura Mansfield

---

current.next = copied_result; 将一个值写入 next，而 dummy = dummy.next; 只是从 next 读取值而不影响其本身的值。 - QBrute

Answer 1

在length方法中，你使用了一个本地可访问的变量dummy来迭代列表中的节点；当你设置dummy = dummy.next时，这会将本地变量的值设置为引用next节点。这与执行dummy.next = null非常不同，后者会影响当前dummy所引用的节点的内容。

因此，你的reverse方法实际上并没有“销毁”原始列表 - 主要问题在于当你完成操作后，head没有被设置为第一个元素。因此，head仍然“指向”函数开始之前相同的节点，现在是最后一个节点。

如果你想原地翻转列表，那么在函数末尾正确更新head就可以正常工作 - 如果你想返回一个翻转后的原始列表的副本而不修改原始列表，则需要复制所有节点。请参见@Hank_interprize关于深/浅拷贝的描述。

- optimus_prime

---

啊，谢谢！我现在完全能看出这两种方法的区别了——改变变量引用和改变实际节点。我会尝试你建议的在最后更新头节点的方法。 - Laura Mansfield

Answer 2

我认为问题在于你并没有将任何新信息复制到新列表中，而是代码只是使用了一个新名称下的相同列表。这可以通过深拷贝来完成。

要创建一个新列表，您需要将旧数据复制到具有全新指针系统的新列表中，并将数据简单地复制到新链表中，这与复制指针不同。

- Hank_Anderson