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

Question

我也看到过类似的问题，但 none 的答案确实解决了我的困惑。

我正在研究一些链表内容，尝试编写方法来解决类似 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;
}

所以，我显然不了解 LinkedLists 的一些基本知识。

为什么我的 reverse() 方法会破坏原始列表，而我的 length() 方法却没有？
在不破坏原始链表的情况下为链表编写反向方法的唯一方法是在您的main方法中复制原始链表并反向复制？

如有任何帮助或资源，我们将不胜感激。谢谢！

Answer 1

我认为这里的问题是您实际上并没有将任何新信息复制到新列表中，而是代码只是在新名称下使用与以前相同的列表。这可以通过深拷贝来完成。

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

Answer 2

在 length 方法中，您使用名为 dummy 的本地可访问变量来遍历列表中的节点；当您设置 dummy = dummy.next 时，这会将局部变量的值设置为引用 next 节点。这与 dummy.next = null 之类的操作非常不同，后者会影响 dummy 当前引用的节点的内容。

为此，您的 reverse 方法实际上并不是 'destroy' 原始列表 - 主要问题是 head 没有被设置为第一个元素，当您完了。因此，head 仍然 'points' 到它在函数启动之前所做的同一节点，现在是最后一个节点。

如果你想就地反转列表，那么只需在函数结束时正确更新 head 就可以了 - 如果你想 return 原件的反转副本在不修改原始列表的情况下，您需要复制所有节点。请参阅@Hank_interprize 对 deep/shallow 份的描述。

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

why does one method destroy my linked list while another does not?

java

linked-list

singly-linked-list