福州企业网站建站系统,电商网站是获取流量,国内最最早做虚拟货币的网站,广告公司的经营范围有哪些大家好我是苏麟 , 今天聊一聊链表反转拓展问题 .
反转链表拓展问题
1.指定区间反转
描述 :
给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。
题目…大家好我是苏麟 , 今天聊一聊链表反转拓展问题 .
反转链表拓展问题
1.指定区间反转
描述 :
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
题目 :
LeetCode 92.反转链表 : 92. 反转链表 II 牛客 BM2 链表内指定区间反转 : 分析 :
这里的处理方式也有多种甚至给个名字都有点困难干脆就分别叫穿针引线法和头插法吧。穿针引线本质上就是不带有节点的方式来实现反转而头插法本质上就是带头结点的反转。
头插法
这个方法的缺点是:
如果 left 和 right 的区域很大恰好是链表的头节点和尾节点时找到left 和 right 需要遍历一次反转它们之间的链表还需要遍历一次虽然总的时间复杂度为 O(N)但遍历了链表 2次p不可以只遍历一次呢? 答案是可以的。我们依然画图进行说明我们仍然以方法一的序列为例进行说明。 反转的整体思想是在需要反转的区间里每遍历到一个节点让这个新节点来到反转部分的起始位置。 下面的图展示了整个流程。 这个过程就是前面的带虚拟结点的插入操作每走一步都要考虑各种指针怎么指既要将结点摘下来接到对应的位置上还要保证后续结点能够找到请读者务必画图看一看想一想到底该怎么调整。
代码如下 :
/*** 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 reverseBetween(ListNode head, int left, int right) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;for (int i 0; i left - 1; i) {pre pre.next;}ListNode cur pre.next;ListNode next;for (int i 0; i right - left; i) {next cur.next;cur.next next.next;next.next pre.next;pre.next next;}return dummyNode.next;}
}
2.单链表加一
描述 :
给定一个用单链表表示的整数然后把这个整数加一。
题目 :
LeetCode 66.加一 :
66. 加一 LeetCode 369.给单链表加一 : 369. 给单链表加一 牛客 NC189 给单链表加一 : 分析 : 我们先看一下加法的计算过程:
计算是从低位开始的而链表是从高位开始的所以要处理就必须反转过来此时可以使用栈也可以使用链表反转来实现。
基于栈实现的思路不算复杂先把题目给出的链表遍历放到栈中然后从栈中弹出栈顶数字 digit加的时候再考虑一下进位的情况就ok了加完之后根据是否大于0决定视为下一次要进位 .import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * return ListNode类*/public ListNode plusOne (ListNode head) {// write code here/**把数字压入栈中*/StackInteger s new Stack();while(head!null){s.push(head.val);head head.next;}ListNode d new ListNode(-100);ListNode p d;//carry代表进位int carry 0;//x代表要加的1int x 1;while(!s.empty() || carry 1){int y s.empty() ? 0 : s.pop() ;int num carry x y;carry num 10 ? 1 : 0;num num 10 ? num-10 : num;//头插ListNode temp new ListNode(num);temp.next p.next;p.next temp;x 0;}return d.next;}
}
基于链表反转实现 如果这里不使用栈使用链表反转来实现该怎么做呢?很显然我们先将原始链表反转这方面完成加1和进位等处理完成之后再次反转。本实现作为一个作业请读者完成。
这期就到这里 , 下一关见!
