leetcode：反转链表II，用C++ 实现

反转链表 II

问题描述

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

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(ListNode *x) : val(x->val), next(x->next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr || left == right) {
            return head;
        }

        ListNode dummy(0); // 创建一个虚拟头节点，简化边界条件处理
        dummy.next = head;
        ListNode* prev = &dummy; // prev 指向 left 节点的前一个节点

        // 将 prev 移动到 left 节点的前一个位置
        for (int i = 0; i < left - 1; ++i) {
            prev = prev->next;
        }

        // 开始反转，curr 指向当前要反转的节点
        ListNode* curr = prev->next;
        for (int i = 0; i < right - left; ++i) {
            ListNode* temp = curr->next; // 临时保存当前节点的下一个节点
            curr->next = temp->next; // 将当前节点的下一个节点指向 temp 的下一个节点
            temp->next = prev->next; // 将 temp 的下一个节点指向 prev 的下一个节点
            prev->next = temp; // 将 prev 的下一个节点指向 temp
        }

        return dummy.next; // 返回虚拟头节点的下一个节点，即新的头节点
    }
};

代码解析

1. 创建一个虚拟头节点 dummy，其 next 指针指向真实的头节点 head，这样可以避免处理 head 为 nullptr 的特殊情况。
2. 使用 prev 指针遍历至 left 节点的前一个节点。
3. 使用 curr 指针指向 left 节点，开始进行反转操作。
4. 在 left 和 right 之间进行节点的逐个反转，每次将 curr 的 next 节点摘出来插入到 prev 和 curr 之间，更新 curr 的 next 指针。
5. 经过 right - left 次操作后，完成了从 left 到 right 的链表反转。
6. 最后返回 dummy.next，即新的头节点。