通过递归反转单链表

Question

这是递归反转单向链表的代码：

public static LinkedListNode reverse_recursive(
      LinkedListNode head) {

    if (head == null || 
        head.next == null) {
        return head;
    }

    LinkedListNode reversed_list = 
      reverse_recursive(head.next);

    head.next.next = head;
    head.next = null;
    return reversed_list;
  }

我知道递归不是解决此问题的最佳方法，但我无法弄清楚代码 "head.next.next=head" 在做什么。我很困惑，请帮我理清思路。谢谢！

Answer 1

head --> A
         .next --> B
                   .next --> C

因此，在上面的示例中，head.next 引用了节点 B，而 head.next.next 引用了节点 C。

head.next.next = something

因此相当于

nodeB.next = something

在您的代码中，something 是 head。而head引用了节点A。所以它给节点B的下一个节点赋了一个新值，这个新值如果节点A：

head --> A <---------------
         .next --> B      |
                   .next --

下面的指令是

head.next = null, which thus leads to

head --> A <---------------
                   B      |
                   .next --

Answer 2

head.next.next = head

正在将当前节点（头）分配为递归最后访问的节点的link。

递归将从列表中的最后一个节点开始，并在第一个节点结束。

假设您有 linked 列表 A --> B --> C --> D --> NULL

会从node D开始反转上述列表，由于节点D的next是null，递归会立即移动到下一个节点，node C

会发生什么事情是它要拿人头（现在是node C），并分配为node D的next

这将发生，直到没有更多的节点需要遍历

Answer 3

public static LinkedListNode reverse_recursive(LinkedListNode head) {
if (head == null || head.next == null) {
    return head;
}

如果节点（在我们的例子中是head）等于null或者下一个节点等于null （意味着只有一个节点）然后 return 那个节点，因为你不能反转空引用或只有一个节点的列表（基本上它已经被反转）。这是递归解决方案的基本情况。

LinkedListNode reversed_list = reverse_recursive(head.next);

我们将下一个节点发送到递归函数中，例如如果我们的列表有三个节点 1->2->3 那么我们将把第二个节点发送到 reverse_recursive 函数。该函数将 return 3->2 和 reversed_list 指向节点 3。现在我们需要将节点 1 连接到反向列表 3->2.

head.next.next = head;

head.next (node 2) 将指向 (head.next.next) node 1 (head).

head.next = null;

由于节点 1 是最后一个节点，它应该指向 null，这意味着没有更多的节点。

return reversed_list;

而现在我们只需要return正确的引用（反转列表的第一个节点）。

通过递归反转单链表

reversing a singly linked list by recursion

java

recursion

singly-linked-list