92. 反转链表 II - 力扣（LeetCode）
相关题目：206. 反转链表 - 力扣（LeetCode）
解法：
/*** 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) {ListNode *dummyNode = new ListNode(-1);dummyNode->next = head;ListNode * tmp = head;ListNode * left_p = nullptr;ListNode * right_p = nullptr;//记录left_pre_p，right_post_p，可以节省一遍遍历操作ListNode * left_pre_p = dummyNode;ListNode * right_post_p = nullptr;int cnt = 1;while (1) {if (cnt == left - 1) {left_pre_p = tmp;}if (cnt == left) {left_p = tmp;}if (cnt == right) {right_p = tmp;}if (cnt == right + 1) {right_post_p = tmp;break;}cnt += 1;tmp = tmp->next;}reverseBetweenCore(left_p, right_p);left_pre_p->next = right_p;left_p->next = right_post_p;return dummyNode->next;}void reverseBetweenCore(ListNode * left, ListNode * right) {ListNode * pre = nullptr;ListNode * cur = left;//这个条件是错误的，因为 ListNode * post = cur->next，会改变right->next，//所以这个条件不会发生// while (cur != right->next) {// ListNode * post = cur->next;// cur->next = pre;// pre = cur;// cur = post;// }while(cur != right) {ListNode * post = cur->next;cur->next = pre;pre = cur;cur = post;}cur->next = pre;}
};总结：
计算时间复杂度O(N)，空间复杂度O(1)，相关题目解法：反转链表（206）-CSDN博客。