java - 通过递归反转单链表

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”在做什么。我很困惑，请帮我理清思路。谢谢！

标签： javarecursionsingly-linked-list

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