求一个方法，用递归将链表逆序，并返回逆序的结果，除了用全局变量

Question

求诸位大神解答

Answer 1

如果不用全局遍历，你可以把中间指针传入到递归函数参数中，也能达到类似全局变量的效果。

Node link_reverse(Node p, Node q)
{
    if (q == NULL) return p;
    
    Node nq = q->next;
    q->next = p;
    
    return link_reverse(q, nq);
}

调用

Node new_head = link_reverse(NULL, link);

Answer 2

递归和数学归纳法差不多，从最简单情况递推
下面是伪代码：

1. 单节点的逆序还是单节点：reverse(n1) = n1

2. 两个节点的逆序等于两个交换： reverse(n1->n2) = n2->n1

3. 根据1，n2 等于自己的逆序，所以： reverse(n1->n2) = reverse(n2)->n1

这时已经覆盖了n2不是单个节点时的情况，改写成真正的代码就是递归算法了。