java递归地反转只有两个指针返回的linkedlist？

Question

我试图递归地反转一个只有两个指针的linkedlist。实际上，每个递归调用都会临时生成第三个指针来辅助它。我有一个特定的算法，我正试图使它遵循this。在堆栈上运行时，程序运行良好，但在堆栈下运行时，我的返回似乎没有任何作用：

public static void main(String[] args)
   {
      ListNode head = new ListNode("hello", null);
      head = new ListNode("foo", head);
      head = new ListNode("boo", head);
      head = new ListNode("nonsense", head);
      head = new ListNode("computer",
         new ListNode("science",
         new ListNode("java",
         new ListNode("coffee", head))));
//head is [computer, science, java, coffee, nonsense, boo, foo, hello]

System.out.print("recur with 2 pointers: \t\t\t\t");
      head = recurTwoPointers(null, head);
      print(head);

public static ListNode recurTwoPointers(ListNode prev, ListNode head)
   {
      if(head == null){
         return head;
      }
      ListNode next = head.getNext();
      head.setNext(prev);
      recurTwoPointers(head, next);
      return next;
   }

我尝试了我能想到的各种回报组合。当程序进入堆栈时，它似乎撤销了它所做的事情，并且值丢失了。最后，我只回来了

[science, computer]

而不是

[hello, foo, boo, nonsense, coffee, java, science, computer]

Answer 1

要反转长度为N的列表，请执行以下操作：

如果N=1，则返回未修改的列表

否则，删除并保存列表中的第一项，然后反转长度为N-1的剩余列表。将保存的元素添加到末尾后返回已反转的列表