翻转链表-递归实现-图解

弹栈返回节点⑤，将④节点的next指向③，③节点的next指向null

2

5

弹栈返回节点⑤，将②节点的next指向①，①节点的next指向null

弹栈返回节点⑤，将⑤节点的next指向④，④节点的next指向null

3

4

 reserveNodeList（⑤）

至此弹栈完毕，返回的节点即为翻转后的尾节点，翻转代码在于交换节点的引用关系，压栈拿到的尾节点实际是压栈不停地next拿到的尾节点，最终作为反转后的链表的头结点

因为递归程序有一个 reserveNodeList(head.next);此处在遇到程序出口前会不停地压栈如左图所示，执行直到遇到出口代码：if(head==null||head.next==null)  return head；最终会遇到尾节点⑤，因为节点⑤在原链表中指向的是null

弹栈返回节点⑤，将③节点的next指向②，②节点的next指向null

 reserveNodeList（②）

 reserveNodeList（③）

程序从头结点①开始不停地进行压栈调用reverseNodeList()

递归压栈伪代码：public  ListNode reserveNodeList(ListNode head){//递归程序出口if(head==null||head.next==null){return head;}//递归调用ListNode newHeadNode = reserveNodeList(head.next);//节点间的引用交换head.next.next=head;head.next=null;return newHeadNode;}

弹栈返回节点⑤，即newHead为⑤

 reserveNodeList（④）

 reserveNodeList（①）

1