链表递归

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

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

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

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

Answer 2

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

Answer 3

拳头节点会被反转改变，所以它是一个in-out参数。 In java: in-parameter + result:

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

显示的代码loops/recurses很多。原因是递归是在 rest 上完成的，然后第一个元素附加在尾部。 很不自然，不自然。

对于递归解决方案，应该采用更自然的解决方案。对于此类递归解决方案，额外的参数会有所帮助。这里我们有一个待办事项列表和一个已完成列表作为参数。

现在可以延迟，使用"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是to-dos的子列表，reversed是已经反转节点的部分结果

这称为尾递归，因为最后有一个递归调用。所以它可以很容易地迭代地写成一个循环。

链表递归

LinkedList Recursion

java

linked-list