反转链表2（92）

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博客。