在不改变原始链表的情况下反转 Java 中的链表

Question

我正在尝试反转一个有效的链表，但是当我尝试打印原件时，它失败了（只打印头部）。我的问题是，为什么倒车会影响原来的。下面是我的代码。 LinkedList是我自己的class，Node也是。在反转之前，如果我尝试打印我的列表，那是可行的。

public static void main(String[] args) {
    LinkedList list;
    ...
    Node head = list.getHead();
    Node rev = reverse(head);
    Node temp = rev;
    while (temp != null) {
        System.out.println(temp);
        temp = temp.next;
    }

    temp = head;
    while (temp != null) {
        System.out.println(temp);
        temp = temp.next;
    }
}

private static reverse(Node head) {
     // Reversing the linked list
}

编辑:: 这似乎是 Java 的事情。 Java 通过引用传递一个对象。当我将 head 作为参数传递时，它是通过引用传递的，对它所做的任何更改都会反映在调用函数中。执行 Node h = head 然后将 h 作为参数传递也不起作用，因为 h 与 head 是同一个对象。我能想到的唯一选择是创建一个新对象，将链表复制过来并将其作为参数传递。

我的问题变成了，有没有更好的解决方案？

Answer 1

要理解它，请将您的列表想象成这样

list (list.head =a) --> a (a.next=b) --> b (b.next= c) -> c (c.next = null)

如果你得到了头，那么你就得到了object'a'。那么你在修改object'a'。所以你可以看到你正在通过这样做来编辑列表。

您需要做的是：得到头创建副本反向复制获取下一个项目复制它反转它加入它到最后等等

由于您使用的是自己的 classes 而不是 java collections classes，最简单的方法是确保 reverseNode() 仅编辑您传递给它的副本，以及 returns 副本。首先确保你的节点 class 有一个构造函数复制另一个节点，然后做这样的事情：

private static Node reverse(Node original) 
{
  Node retval = new Node(original);
  // or you could use clone () as Bhavik suggested, if your Node class implements it
  // modify retval 
  // I haven't shown code to reverse it as I assume you already have that and you didnt specify if it was a bidirectional list or just one direction.

  return retval;
}

或者你可以在你的节点中添加一个静态方法 class 来构造一个颠倒的新节点:

static Node createReverse(Node n) 
{
    return new Node(n.data,n.next,n.prior);
}

或节点 class 的非静态方法 returns 自身的反向副本；

Node createReverse()
{
   return new Node(this.data,this.next,this.prior);
}

但是你应该考虑到这会变得非常难看，因为你的副本仍然会有指向现有列表的指针！

更好的方法可能是创建一个新的空列表，然后从原始列表的末尾开始，制作一个副本，并将其添加到新列表的开头。

您可以使用递归来执行此操作，但可能很容易运行内存不足。

但与其手动执行此操作，不如查看 java.util 包并切换到使用其中一种 LinkedList 和列表项类型。这些classes已经解决了做这件事的所有问题。

然后你可以（如果你需要保持原始列表不变）： - 复制整个列表。 - 反向复制如下

如果你不介意保留原件，那么只需使用列表中的此方法（如下），无需复制。

来自 java.util.Collections:

Collections.reverse(List a_list);

Collectionsclass会根据双向、单向等情况选择一种高效的方式来反转列表

Answer 2

Chunko 的回答是正确的，因为您应该创建节点的副本，而不是仅仅传递对它们的引用。
但是，我认为您可能想多了：

LinkedList reversedList = new LinkedList();
for (int i = originalList.size()-1; i >= 0; i--) {
    reversedList.add(list.get(i));
}

Java 的 LinkedList 没有 getHead() 方法，所以我猜你正在使用一些 homework-related 链表的自定义实现。不过，您的实现应该有一个 add() 方法将新的 Node 附加到列表，以及一个 get(int) 方法 returns 给定位置的项目。
您可以使用这些方法创建一个新列表，并以相反的顺序用原始列表的项目填充它。

在不改变原始链表的情况下反转 Java 中的链表

Reversing a linked list in Java without changing the original

java

linked-list

pass-by-reference