每次循环将curr.next修改为前一节点
因为需要将当前节点的next节点修改为前一节点,所以需要用一个指针prev记录前一节点。同时,由于修改了当前节点的next节点后,无法访问原来的next节点,因此需要一个指针next,在修改前记录原来的next节点
- 时间复杂度:O(n)
- 空间复杂度:O(1)
n(1) -> n(2) -> ... -> n(k) -> n(k+1) <- ... <- n(m)
在m个节点的链表中,对于每次递归处理的节点k,假设节点k之后的节点已经处理完(逆序)。对于节点k,只需修改其next成员,以及节点(k+1)的next成员
n(k)->next->next = n(k);
n(k)->next = NULL;
函数返回逆序后链表的头结点,因此对于n(m),直接返回n(m)
- 时间复杂度:O(n)
- 空间复杂度:O(n)(每次递归函数栈帧都会创建1个局部指针保存逆序后的链表头结点)
注:不能假设对于每次递归处理的节点k,前k-1个节点已经逆序。因为节点k无法访问到前一节点,因此无法将k节点逆序,因此对于节点k+1,前k个节点无法逆序。也不能假设前k个节点已经逆序,因为如果前k个节点已经逆序,对于节点k,将k+1节点逆序,当处理k+1节点时,无法访问到k+2节点