略带困惑请多指教

问题描述：

我这个递归是借助非递归实现，想出来的，需要prev和curr两个指针

（之前以为链表翻转后，指向尾节点的指针会丢掉，才不得已加了prev）

（不知道课上还有个精彩的点：递归的头节点正好指向了已经完成翻转的链表的尾节点）

相当于我每次递归的时候，都带着两条链表进去，一条curr指向的原链表，一条prev指向新链表

终止条件：原链表空了，就直接返回，不用做任何操作

递归的逻辑是：把原链表的头取出来，拼接到新链表的头（即更新一下两条链表的头节点），然后就进下一层递归

我的问题是：这个解法感觉有点奇怪，课上的例题一般都是上层递归对下层递归的结果做逻辑处理后返回，但这个直接就能返回了。。

相关代码：

public ListNode reverseListRecursion(ListNode head) {
    return reverseListRecursion(head,null).getValue();
}

// 队头为key，倒序新队头为value
private Pair<ListNode,ListNode> reverseListRecursion(ListNode head, ListNode prev){
    if (head == null) {
        return new Pair(null,prev);
    }
    ListNode subList = head.next;
    head.next = prev;
    prev = head;
    return reverseListRecursion(subList,prev);
}

eyuji 2023-08-23

源自：动态数据结构基础：链表 3-3 翻转链表的递归实现

收起

1回答

liuyubobobo 2023-08-24 01:03:02

抱歉，我不是特别理解你的问题。

如果你的问题是，为什么最后能直接返回 reverseListRecursion(subList,prev)，你觉得返回一个递归函数“不舒服”，你可以这么做：

Pair<ListNode,ListNode> reverseListRecursion(ListNode head, ListNode prev){     
    if (head == null) {         
        return new Pair(null,prev);     
    }    
    
    // 递归的逻辑处理 
    ListNode subList = head.next;     
    head.next = prev;      
    prev = head;     
    
    // 先把递归的结果存起来，再返回
    ListNode res = reverseListRecursion(subList,prev); 
    return res;
}

如果你觉得先做递归逻辑处理，再递归调用"很奇怪"，实际上，这是很正常的，我们后续学习的快排就是这个样子。

private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        
    if(l >= r) return;
    
    // 逻辑处理
    int p = partition(arr, l, r);
    
    // 递归调用    
    sort(arr, l, p - 1);
    sort(arr, p + 1, r);
}

更广义的，基于树结构的“先序遍历”递归算法，都是如此。

==========

不要去记什么先处理后递归这样的“顺序”，这不是逻辑。正是因为如此，在这个课程中，我从来不会强调什么“模板”，什么“记住这段代码”。这都不是学习计算机的正确方式。学习计算机，尤其是学习算法，关键是理清逻辑。你要达到什么目的，为了达到这个目的，你的逻辑是怎样的，为什么逻辑是这样的。代码的顺序只是逻辑的体现而已。

继续加油！：）

收起回答