河南网站制作团队,中国500强排名完整版,15年做那些网站致富,做网站要什么资质题目#xff1a;
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转#xff0c;要求时间复杂度 O(n)#xff0c;空间复杂度 O(1)。 例如#xff1a; 给出的链表为 1→2→3→4→5→NULL#xff0c;m2#xff0c;n4 返回 1→4→3→2→5→NULL
数据范围#xff…题目
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转要求时间复杂度 O(n)空间复杂度 O(1)。 例如 给出的链表为 1→2→3→4→5→NULLm2n4 返回 1→4→3→2→5→NULL
数据范围 链表长度 0 size ≤10000m≤n≤size链表中每个节点的值满足∣val∣≤1000
要求时间复杂度O(n) 空间复杂度O(n)
进阶时间复杂度O(n)空间复杂度O(1) 示例1
输入{1,2,3,4,5},2,4返回值{1,4,3,2,5}
示例2
输入{5},1,1返回值{5} 解题思路
这个是在 《单向链表翻转》基础上增加了些难度指定了区间内的翻转。
首先考虑链表的有效性和m、n 的值合法性
接着考虑m 的值m 可能为1则要求链表从头开始翻转
如果m 不为0那就是将量表分为 3 节头、中、尾三部分。 代码
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * param m int整型 * param n int整型 * return ListNode类*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {if (m n || NULL head)return head;struct ListNode* rHead head;struct ListNode* rTail NULL;for (int i 1; NULL ! head i m; i) { //找到rTail和需要翻转的headrTail head;head head-next;}if (NULL rTail) { //第一个就需要翻转rHead NULL;rTail NULL;}struct ListNode* mHead NULL;struct ListNode* mTail NULL;struct ListNode* mp NULL;for (int i m; NULL ! head i n; i) { //进行翻转mp head;head head-next;mp-next mHead;mHead mp;if (NULL mTail) {mTail mp;}}if (NULL ! rTail) { //拼接m之前的连接rTail-next mHead;}if (NULL ! mTail) { //拼接n后面的链表mTail-next head;}if (NULL rHead) { //如果从第一个开始翻转rHead mHead;}return rHead;
}
运行结果 是否还有好的方法请大神们不吝赐教
