BM2 链表内指定区间反转
解题思路:[头插法]
在学会了BM1.反转链表之后,要解决这个问题就很简单了,前一题是整个链表反转,这一题是部分反转,这上一题就是这道题的前置问题啊。那我们肯定是要先找到了第m个位置才能开始反转链表,而反转的部分就是从第m个位置到第n个位置,反转这部分的时候就参照BM1.反转链表
具体做法:
- step 1:我们可以在链表前加一个表头,后续返回时去掉就好了,因为如果要从链表头的位置开始反转,在多了一个表头的情况下就能保证第一个节点永远不会反转,不会到后面去。
- step 2:使用两个指针,一个指向当前节点,一个指向前序节点。
- step 3:依次遍历链表,到第m个的位置。
- step 4:对于从m到n这些个位置的节点,依次断掉指向后续的指针,反转指针方向。
- step 5:返回时去掉我们添加的表头。
从m到n的反转部分着重理解
# 从m反转到n,-1->1->2->3->4->5,m=2,n=4
for i in range(m,n):
temp = cur.next #第一次循环 pre:1 cur:2 temp:3
cur.next = temp.next # 2->4 !!!赋值号左边代表指针的指向,右边代表指针所指的元素。比如temp:3 temp.next:4, cur.next代表2->3的指向。
temp.next = pre.next # 3->2
pre.next = temp # 1->3
# 第一次循环结束后变成-1->1->3->2->4->5
Python代码
class Solution:
def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
# 加个表头 -1->1->2->3->4->5
res = ListNode(-1)
res.next = head
# 前序节点
pre = res
# 当前节点
cur = head
# 找到m
for i in range(1,m):
pre = cur
cur = cur.next
# 从m反转到n,-1->1->2->3->4->5,m=2,n=4
for i in range(m,n):
temp = cur.next #第一次循环 pre:1 cur:2 temp:3
cur.next = temp.next # 2->4 !!!赋值号左边代表指针的指向,右边代表指针所指的元素。比如temp:3 temp.next:4, cur.next代表2->3的指向。
temp.next = pre.next # 3->2
pre.next = temp # 1->3
# 返回去掉表头
return res.next
C++代码
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;
}
};
复杂度分析:
- 时间复杂度:O(n),最坏情况下需要遍历全部链表节点,比如m为链表最后一个位置,或者n为链表最后一个位置时
- 空间复杂度:O(1),常数级指针变量,无额外辅助空间使用