Java 中的反向链表

Question

我正在查看这篇文章中的解决方案 递归地反转 Java 中的链表< /a>

我复制了下面的解决方案之一。我已经实现了并且效果很好。

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.Next = list;

    return reverseRest;
}

然而，我不明白的是最后几行。

secondElem.next = list;
return reverseRest;

看来我们根本没有返回第二个Elem？但我调试了代码，看起来第二个Elem已经在reverseRest里面了。这是因为它是 Java 中的值引用，并且在应用 secondElem.Next=list 时会自动更新吗？

Answer 1

不要考虑传递语义，而是考虑内存中的对象和包含对它们的引用的变量。

初始状态：

(list)
   |
   V
[  1  ] -> [  2  ] -> ... -> [  N  ]

list.next = null;之后：

(list)   (secondElem)
   |          |
   V          V
[  1  ]    [  2  ] -> ... -> [  N  ]

递归调用之后：

(list)   (secondElem)      (reverseRest)
   |          |                 |
   V          V                 V
[  1  ]    [  2  ] <- ... <- [  N  ]

之后的最终状态代码>secondElem.Next = list;:

(list)   (secondElem)      (reverseRest)
   |          |                 |
   V          V                 V
[  1  ] <- [  2  ] <- ... <- [  N  ]

Answer 2

如果您的目标只是反转列表，请使用 Collections.reverse(list)

Answer 3

但是，我不明白的是最后几行。

secondElem.next = 列表；
返回反向休息；

让我一一解释一下你不理解的两行：

1.secondElem.next = list;

我认为第二个Elem的创建引入了额外的复杂性。根本不需要变量 secondaryElem。

代替这个：

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.Next = list;

使用这个：

ListNode reverseRest = Reverse(list.next);    
list.next.next = list;

更容易掌握。最后一行代码清楚地显示了列表反转过程本身！

2. return reverseRest;

看看reverseRest变量的用法&了解它的目的。它的唯一目的是将列表的原始尾部的值渗透到所有递归调用的末尾，以便我们可以将原始尾部（也是新的头）返回到调用 Reverse 函数的主函数。您必须快速理解这一点，因为我们根本没有在递归调用之间更改变量reverseRest的值 - 无论我们从 Reverse(secondElem) 收到什么返回值，我们都会从函数中“按原样”返回它！