题解 | #链表内指定区间反转#

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (head == nullptr || m == n) {
        return head;
    }

    ListNode* dummy = new ListNode(0); // 虚拟头结点
    dummy->next = head;

    ListNode* pre = dummy; // 保存m位置前一个节点的指针
    ListNode* curr = head; // 当前节点指针
    int count = 1; // 计数器

    // 找到m位置前一个节点
    while (count < m) {
        pre = curr;
        curr = curr->next;
        count++;
    }

    ListNode* start = pre; // 反转区间的前一个节点
    ListNode* tail = curr; // 反转区间的尾节点

    // 反转区间内的节点
    for (int i = m; i <= n; i++) {
        ListNode* nextTemp = curr->next;
        curr->next = pre;
        pre = curr;
        curr = nextTemp;
    }

    // 连接反转区间和后续节点
    start->next = pre;
    tail->next = curr;

    ListNode* newHead = dummy->next;
    delete dummy;

    return newHead;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "原链表：";
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

    ListNode* newHead = reverseBetween(head, 2, 4);

    std::cout << "反转后的链表：";
    curr = newHead;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

    // 释放内存
    curr = newHead;
    while (curr != nullptr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }

    return 0;
}