递归链表翻转
给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。
示例 1:
1 | 输入:head = [1,2,3,4,5] |
示例 2:
1 | 输入:head = [1,2] |
示例 3:
1 | 输入:head = [] |
基础递归公式如下
前置递归
1 | function reverse(head){ |
使用[1,2,3,4,5]作为测试用例,输出结果如下
1 | last-- [5] |
做一个灵魂画手,帮助记忆。
由于是前置递归,代码由下而上进行运行,每一步都会将head节点与上一个节点进行翻转,并将head节点指向null
head节点信息由调用栈的函数持有
后置递归
1 | // 后置递归 |
灵魂画手又来了
迭代
1 | // 迭代 |
翻转链表前N个节点
1 | 输入 [1,2,3,4,5] 3 |
前置递归
1 | function ListNode(val, next) { |
灵魂画图,有点难以理解啊