LinkedList Recursion

Question

public class LinkedList {
    Node head = null;
    int nodeCount= 0;
    int counter = 0;
    LinkedList() {
        head = null;
    }
   public Node reverseTest(Node L) {
       if(L == null || L.next ==null) {
           return L;
       }
       Node remainingNode =  reverseTest(L.next);
       Node cur = remainingNode;
       while(cur.next !=null) {
           cur=cur.next;
       }
       L.next = null;
       cur.next = L;
       return  remainingNode;
   }
}
public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList FriendList = new LinkedList();
        FriendList.insertNode("First");
        FriendList.insertNode("Second");
        FriendList.insertNode("Third");
        FriendList.insertNode("Fourth");
        FriendList.reverseTest(FriendList.head);
        // FriendList.copyObject(FriendList.head);
        String NameList = FriendList.toString();
        System.out.println(NameList);
        System.out.println("Finish");
    }
}

困惑:

在返回本行第一个L值后递归的reverseTest方法中

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

我们将值传递给这一行的remainingNode

Node remainingNode =  reverseTest(L.next);

然后复制到cur变量

 Node cur = remainingNode;

当我们到达线

cur.next = L; 

它用L更新cur.next，但它也更新

remainingNode.next = L

我不明白。如何?谁能告诉我该查什么?

Answer 1

当前节点和剩余节点指向相同的内存地址。无论你对其中一个做什么都会影响到另一个。您希望它们指向两个不同的内存位置。

Answer 2

在Node cur = remainingNode;和cur.next = L之间有一个while循环:

while(cur.next !=null){
    cur=cur.next;
}

因此，cur和remainingNode不是指向同一个节点。cur现在指向从remainingNode开始的列表的最后一个节点。

Answer 3

首先，头部节点将被反转改变，因此它是一个输入输出参数。In -parameter + result:

friendList.head = FriendList.reverseTest(FriendList.head);

所示代码循环/递归频繁。原因是在剩下的元素上完成递归，然后在尾部追加第一个元素。非常不自然，间接的。

对于递归解，我们应该寻找更自然的解。对于这样的递归解，一个额外的参数会有所帮助。这里我们有一个to-do列表和一个done-list作为参数。

现在你可以延迟，使用"future"结果:

public Node reverseTest(Node L) {
      return reverseRecursively(L, null);
}
private Node reverseRecursively(Node node, Node reversed) {
      if (node == null) {
          return reversed;
      }
      Node next = node.next;
      node.next = reversed;
      reversed = node;
      return reverseRecursively(next, reversed);
}

这里node将是待办事项的子列表，reversed将是已经反转的节点的部分结果。

这被称为尾部递归，因为在最后有一个递归调用。因此，它可以很容易地迭代编写为单个循环。