国航网站建设,基于ssh框架的网站开发流程,沧州房产信息网,小程序云服务器多少钱目录一. 递归反转整个链表1. 思路简述2. 代码3. 总结二. 反转链表前 N 个节点1. 思路简述2. 代码3. 总结三、反转链表的一部分1. 思路简述2. 代码3.总结四、从节点M开始反转后面的链表1. 思路简述2. 代码3.总结一. 递归反转整个链表
题目链接#xff1a;https://leetcode.cn/…
目录一. 递归反转整个链表1. 思路简述2. 代码3. 总结二. 反转链表前 N 个节点1. 思路简述2. 代码3. 总结三、反转链表的一部分1. 思路简述2. 代码3.总结四、从节点M开始反转后面的链表1. 思路简述2. 代码3.总结一. 递归反转整个链表
题目链接https://leetcode.cn/problems/reverse-linked-list/
1. 思路简述
所谓递归就像那句歌词一样“一层一层剥开我的心”我们从第一个节点一直向下探索发现节点5。现在想如果是单个节点那反转链表其实就相当于自身本身也就是不用动了。这里考虑一个临界情况如果传进的参数head指针是null那也不用动了直接返回其本身就可以。来到倒数第二层也就是节点4现在情况变成了节点有2个的链表现在需要反转那么我们只需要将中间的指针做一个反转就好了而当前传进来的指针head其实是节点4的head指针那么就有head.next.next head最后将节点4的后继赋值为空head.next null这表示这一阶段有2个节点的链表已经反转完成。如果链表只有两个节点直接输出就可以。重复上面步骤直到最后整个链表都反转了
2. 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution { public ListNode reverseList(ListNode head) {//从后向前一点点的进行反转//先分析特殊情况链表有一个节点或者没有节点直接返回头结点if(head null || head.next null)return head;else{//last为反转链表之后的头指针ListNode last reverseList(head.next);head.next.next head;head.next null;return last;}}
}3. 总结
时间复杂度o(n)空间复杂度o(n)需要用栈第一次做的时候还以为是逆向输出整了半天搞错了。对递归的边界条件掌握的还是不好像head null这一块博主当时就没想到与head.next进行合并。head.next null;一定要注意否则会出现成环的现象
二. 反转链表前 N 个节点
题目链接没有链接给一个函数名public static ListNode reverseN(ListNode head,int n)自己去练吧。
1. 思路简述
本质和反转链表差不多只是在边界值的地方需要注意
2. 代码 //存放需要逆转链表的后继第一个节点public static ListNode successor null;public static ListNode reverseN(ListNode head,int n){//逆转前n个节点if (n 1) {successor head.next;return head;}//递归将下一个节点放进去ListNode last reverseN(head.next, n - 1);head.next.next head;head.next successor;return last;}3. 总结
也就是反转链表只是每次反转完head后面要接后继节点后面的一段不需要反转的链表就变了这一点。时间复杂度o(n)空间复杂度o(n)需要用栈
三、反转链表的一部分
题目链接https://leetcode.cn/problems/reverse-linked-list-ii/
1. 思路简述
将问题转换成反转前n个节点的问题。
2. 代码 //存放需要逆转链表的后继第一个节点public static ListNode successor null;public static ListNode reverseN(ListNode head,int n){//逆转前n个节点if (n 1) {successor head.next;return head;}//递归将下一个节点放进去ListNode last reverseN(head.next, n - 1);head.next.next head;head.next successor;return last;}ListNode reverseBetween(ListNode head, int m, int n) {// 当m为1的时候装换成了反转前面几个节点的链表的问题if (m 1) {return reverseN(head, n);}// 将前面不需要反转的链表和后面反转过的链表接在一起head.next reverseBetween(head.next, m - 1, n - 1);return head;}3.总结
head.next reverseBetween(head.next, m - 1, n - 1); 为什么是head.next呢看边界情况m 1时返回的是后面已经反转过的链表也就是说前面的链表压根不需要反转只要把它们拼接在一起就行了。再说为什么是m - 1的问题每递归一次新链表就会从前面缩短一节那么对于新链表来说就是从第m-1个节点开始反转到第n - 1个节点结束反转。这里的关键是链表从头开始缩短了所以m - 1 和 n - 1都要存在。
四、从节点M开始反转后面的链表
题目链接没有链接给一个函数名public static ListNode reverseP(ListNode head,int m)自己去练吧。
1. 思路简述
转换成反转单链表的问题
2. 代码 public ListNode reverseList(ListNode head) {//从后向前一点点的进行反转//先分析特殊情况链表有一个节点或者没有节点直接返回头结点if(head null || head.next null)return head;else{//last为反转链表之后的头指针ListNode last reverseList(head.next);head.next.next head;head.next null;return last;}}public static ListNode reverseP(ListNode head, int m){//转换成反转链表的问题if(m 1){return reverseList(head);}head.next reverseP(head.next, m - 1);return head;}3.总结
和上一题差不多一直递归到链表需要反转的地方m 1开始反转整个单链表。
参考https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/di-gui-mo–10b77/
