文章目录
反转链表 ||
题目描述
反转从位置 m 到 n 的链表。（请使用一趟扫描完成反转）。
示例：
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路
使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：
curr：指向待反转区域的第一个节点 left；
next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。
操作步骤：
先将 curr 的下一个节点记录为 next；
执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
执行操作 ③：把 pre 的下一个节点指向 next。
具体代码
代码如下（示例）：
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode *dump = new ListNode(-1, head);
ListNode *pre = dump;
for (int i = 0; i < left - 1; i++) pre = pre -> next;
ListNode *cur, *nex;
cur = pre -> next;
nex = cur -> next;
for (int i = 0; i < right - left; i++){
cur -> next = nex -> next;
nex -> next = pre -> next;
pre -> next = nex;
nex = cur -> next;
}
return dump -> next;
}
};