LinkedList递归

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");

    }
}

混淆：

在reverseTest方法中，它是在从该行返回第一个L值之后递归的。

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

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

Answer 2

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

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

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

Answer 3

首先，头节点将被反转改变，因此它是一个输入-输出参数。在java中: In参数+结果：

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

显示的代码循环/递归很多。原因是递归是在其余部分上完成的，然后第一个元素附加在尾部。非常不自然，间接的。

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

现在可以延迟，使用“未来”结果：

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则是已经反转的节点的部分结果。

这被称为尾递归，因为在末尾有一个递归调用。因此，它可以很容易地写成一个单一的循环。