leetcode 92. 反转链表 II

leetcode 92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

方法一：穿针引线

/**
 * 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 {
private:
    void reverseLinkList(ListNode* head) {
        ListNode* p1 = head;
        ListNode* p2 = nullptr;
        ListNode* temp = nullptr;
        while(p1) {
            temp = p1->next;
            p1->next = p2;
            p2 = p1;
            p1 = temp;
        }
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //注意，由示例可知，left、right是编号不是下标
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode* dummyHead = new ListNode(-1,head);
        ListNode* p1 = dummyHead;
        size_t count = 0;
        
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        while(p1 && count < left - 1) {
            p1 = p1->next;
            ++count;
        }
        ListNode* preLeftNode = p1;
        
        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        while(p1 && count < right) {
            ++count;
            p1 = p1->next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode* leftNode = preLeftNode->next;
        ListNode* rightNext = p1->next;
        preLeftNode->next = nullptr;
        p1->next = nullptr;

        //第 4 步：反转链表的子区间
        reverseLinkList(leftNode);

        // 第 5 步：接回到原来的链表中
        preLeftNode->next = p1;
        leftNode->next = rightNext;

        head = dummyHead->next;
        delete dummyHead;
        dummyHead = nullptr;
        return head;

    }
};

方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)，但遍历了链表 2 次，可不可以只遍历一次呢？答案是可以的。

方法二：一次遍历「穿针引线」反转链表（头插法）

image.png