描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1)。
例如:
给出的链表为 :1→2→3→4→5→NULL, m = 2, n = 4
返回 1→4→3→2→5→NULL.
数据范围: 链表长度 0 < size ≤ 1000,0 < m ≤ 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 个位置才能开始反转链表,而反转的部分就是从第 m 个位置到第 n 个位置,反转这部分的时候就参照反转链表:
while(cur != null){
//断开链表,要记录后续一个
ListNode temp = cur.next;
//当前的next指向前一个
cur.next = pre;
//前一个更新为当前
pre = cur;
//当前更新为刚刚记录的后一个
cur = temp;
}
具体做法:
图示:
代码:
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
//加个表头
ListNode* res = new ListNode(-1);
res->next = head;
//前序节点
ListNode* pre = res;
//当前节点
ListNode* cur = head;
//找到m
for(int i = 1; i < m; i++){
pre = cur;
cur = cur->next;
}
//从m反转到n
for(int i = m; i < n; i++){
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
//返回去掉表头
return res->next;
}
};
运行时间:4ms
超过36.19% 用C++提交的代码
占用内存:428KB
超过68.70%用C++提交的代码
复杂度分析:
时间复杂度: O(n),最坏情况下需要遍历全部链表节点,比如 m 为链表最后一个位置,或者 n 为链表最后一个位置时
空间复杂度: O(1),常数级指针变量,无额外辅助空间使用
方法二:递归(扩展思路)
思路:
我们来看看另一种分析:如果m == 1
,就相当于反转链表的前 n 元素;如果 m != 1
,我们把 head 的索引视为 1,那么我们是想从第 m 个元素开始反转,如果把 head.next 的索引视为1,那相对于 head.next 的反转的区间应该是从第 m − 1 个元素开始的,以此类推,反转区间的起点往后就是一个子问题,我们可以使用递归处理:
当m == 1
,就可以直接反转前 n 个元素。//从头开始往后去掉前面不反转的部分
ListNode node = reverseBetween(head.next, m - 1, n - 1)
而每次反转,如果n == 1
,相当于只颠倒第一个节点,如果不是,则进入后续节点(子问题),因此反转过程也可以使用递归:
n == 1
时,只反转当前头节点即可。//颠倒后续的节点,直到n=1为最后一个
ListNode node = reverse(head.next, n - 1)
具体做法:
代码:
class Solution {
public:
ListNode* temp = NULL;
ListNode* reverse(ListNode* head, int n){
//只颠倒第一个节点,后续不管
if(n == 1){
temp = head->next;
return head;
}
//进入子问题
ListNode* node = reverse(head->next, n - 1);
//反转
head->next->next = head;
//每个子问题反转后的尾拼接第n个位置后的节点
head->next = temp;
return node;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
//从第一个节点开始
if(m == 1)
return reverse(head, n);
//缩减子问题
ListNode* node = reverseBetween(head->next, m - 1, n - 1);
//拼接已翻转
head->next = node;
return head;
}
};
运行时间:4ms
超过36.19% 用C++提交的代码
占用内存:428KB
超过68.70%用C++提交的代码
复杂度分析:
时间复杂度: O(n),最坏情况下递归遍历全部链表节点,比如 m 为链表最后一个位置,或者nnn为链表最后一个位置时
空间复杂度: O(n),遍历全部节点时递归栈深度最坏为 n
官方解释~