java - 在Java中反转链表而不改变原始链表

Question

我试图反转一个有效的链接列表，但是当我尝试打印原件时，它失败了(仅打印头部)。我的问题是，为什么反转会影响原来的。下面是我的代码。 LinkedList是我自己的类，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 作为参数传递时，它是通过引用传递的，对其所做的任何更改都会反射(reflect)在调用函数中。 执行 Node h = head 然后将 h 作为参数传递也不起作用，因为 h 将是与 head 相同的对象。 我能想到的唯一选择是创建一个新对象，复制链接列表并将其作为参数传递。

我的问题是，有更好的解决方案吗？

Answer 1

要理解它，请想象您的列表如下所示

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

如果你得到了头部，那么你就得到了对象“a”。 然后您正在修改对象“a”。 因此您可以看到您正在通过执行此操作来编辑列表。

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

由于您使用的是自己的类而不是 java 集合类，因此最简单的方法是确保 reverseNode() 只编辑您传递给它的类的副本，然后返回该副本。 首先确保您的 Node 类有一个复制另一个 Node 的构造函数，然后执行如下操作:

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;
}

或者您可以在 Node 类中添加一个静态方法来构造一个相反的新节点:

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

或者节点类的非静态方法，它返回自身的反向副本；

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

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

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

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

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

然后你可以(如果你需要保持原始列表不变): - 复制整个列表。 - 反转副本如下

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

来自 java.util.Collections:

Collections.reverse(List a_list);

Collections 类将选择一种有效的方式来反转列表，具体取决于它是双向的、单向的等。