2015网站建设,帝国网站管理 上一条 下一条 链接 信息id 信息发布时间,网站套网站代码,网站制作自己做【问题描述】[简单] 【解答思路】
1. 递归 自底向上 基本条件/终止条件#xff1a;当前节点或者下一个节点null 递推关系#xff1a; head.next.next head
在函数内部#xff0c;改变节点的指向#xff0c;也就是 head 的下一个节点指向 head 递归函数那句
时间…【问题描述】[简单] 【解答思路】
1. 递归 自底向上 基本条件/终止条件当前节点或者下一个节点null 递推关系 head.next.next head
在函数内部改变节点的指向也就是 head 的下一个节点指向 head 递归函数那句
时间复杂度O(N) 空间复杂度O(N)
class Solution {public ListNode reverseList(ListNode head) {//递归终止条件是当前为空或者下一个节点为空if(headnull || head.nextnull) {return head;}//这里的cur就是最后一个节点ListNode cur reverseList(head.next);//这里请配合动画演示理解//如果链表是 1-2-3-4-5那么此时的cur就是5//而head是4head的下一个是5下下一个是空//所以head.next.next 就是5-4head.next.next head;//防止链表循环需要将head.next设置为空head.next null;//每层递归函数都返回cur也就是最后一个节点return cur;}
}
2. 递归 自顶向下
寻找递推关系创建新函数将「自底向上-范式」中的最终结果计算依赖的中间变量提取为函数的参数 - prev为中间变量寻找递归基本情况跳出时返回基本情况的结果与中间变量的计算结果最终结果 - 遍历完毕后返回头节点pre根据函数参数与中间变量重新计算出新的中间变量 - ListNode next node.next;修改参数 - node.next prev;调转方向 第一个指向了null递归调用并返回该处的返回由基本情况条件触发- reverse(node, next); 时间复杂度O(N) 空间复杂度O(N) public ListNode reverseList(ListNode head) {return reverse(null, head);}public ListNode reverse(ListNode prev, ListNode node) {if (node null) {return prev;}// logicListNode next node.next; // node1 next2node.next prev; // 1-null、2-1return reverse(node, next); // 1 2}class Solution {ListNode pre null, tmp null;public ListNode reverseList(ListNode head) {if (head null)return pre;tmp head.next;head.next pre;pre head;head tmp;return reverseList(head);}
}3. 双指针 循环结构
第一个指针叫 pre最初是指向 null 的。第二个指针 cur 指向 head然后不断遍历 cur。每次迭代到 cur都将 cur 的 next 指向 pre然后 pre 和 cur 前进一位。迭代完了(cur 变成 null 了)pre 就是最后一个节点了。 时间复杂度O(N) 空间复杂度O(1)
class Solution {public ListNode reverseList(ListNode head) {//申请节点pre和 curpre指向nullListNode pre null;ListNode cur head;ListNode tmp null;while(cur!null) {//记录当前节点的下一个节点tmp cur.next;//然后将当前节点指向precur.next pre;//pre和cur节点都前进一位pre cur;cur tmp;}return pre;}
}
【总结】
1. 「自顶向下、自底向上、循环结构」三种方法完成
2.递归
在实现递归函数之前有两件重要的事情需要弄清楚:
递推关系一个问题的结果与其子问题的结果之间的关系。 基本情况不需要进一步的递归调用就可以直接计算答案的情况。可理解为递归跳出条件。 一旦我们计算出以上两个元素再想要实现一个递归函数就只需要根据递推关系调用函数本身直到其抵达基本情况。
3.递归模板套路
由下到上
参考链接https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/ 递归学习链接https://blog.csdn.net/dadongwudi/article/details/107649161
