LeetCode:反转区间内的链表

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

反转区间内的链表

题目链接

92. 反转链表 II - 力扣（LeetCode）

方法一：拆开+反转+连接

思路

Step1：将要反转的区间链表分离出来作为一个单独的链表

Step2：将分离出的链表进行反转

Step3：将反转好区间链表连接回去

代码

    void reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* cur = head;while(cur) {ListNode* ne = cur->next;cur->next = prev;prev = cur;cur = ne;}}ListNode* reverseBetween(ListNode* head, int left, int right) {if(head == nullptr || head->next == nullptr || right == left) {return head;}//设置一个哨兵头节点ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* prev = dummyNode;for(int i = 1; i < left; ++i) {prev = prev->next;}ListNode* leftNode = prev->next;ListNode* rightNode = leftNode;for(int i = 0; i < right - left; ++i) {rightNode = rightNode->next;}ListNode* succ = rightNode->next;prev->next = nullptr;rightNode->next = nullptr;reverseList(leftNode);prev->next = rightNode;leftNode->next = succ;return dummyNode->next;}

复杂度分析

时间复杂度：O(N),这里找四个节点的位置，和反转链表都是O(N)级别，所以时间复杂度就是O(N)级别

空间复杂度：O(1),这里在原地进行反转，只使用了额外的四个指针变量

方法二：头插法

思路

这里的思路简单来说就是：对于反转的区间通过头插的方式进行反转

对于区间中的每个节点进行如下操作，也就是进行一个头插：

Step1：当前节点的next指向next节点的next

Step2：next节点的next指向当前节点

Step3：pre节点的next指向next节点

代码

    ListNode* reverseBetween(ListNode* head, int left, int right) {if(head == nullptr || head->next == nullptr || left == right) {return head;}ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;ListNode* prev = dummyNode;for(int i = 1; i < left; ++i) {prev = prev->next;}ListNode* cur = prev->next;ListNode* ne;for(int i = 0; i < right - left; ++i) {ne = cur->next;cur->next = ne->next;ne->next = prev->next;prev->next = ne;}return dummyNode->next;}

复杂度分析

时间复杂度：O(N), 最坏情况下也只会遍历一次，比方法一的时间复杂度更优

空间复杂度：O(1), 依旧是使用常熟个指针变量