反转链表II
- 题解1 一遍遍历(穿针引线)
给你单链表的头指针
head
和两个整数
left
和
right
,其中
left <= right
。请你反转从位置
left
到位置
right
的链表节点,返回
反转后的链表 。
提示:
- 链表中节点数目为
n
- 1 <=
n
<= 500 - -500 <=
Node.val
<= 500 - 1 <=
left <= right <= n
进阶: 你可以使用一趟扫描完成反转吗?
题解1 一遍遍历(穿针引线)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(left == right) return head;
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* nex;
for(int i = 0; i < right-left; i ++){
// 穿针引线:
// cur是left对应的结点,没变过
// 实际上每次操作都只和cur->next(nex)\pre->next\nex->next有关(3个链)
nex = cur->next;
cur->next = nex->next;
nex->next = pre->next;
pre->next = nex;
}
return dummynode->next;
}
};