【C++】每日一题 92 反转链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】每日一题 92 反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int _val) {
        val = _val;
        next = nullptr;
    }
};

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

    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;

    for (int i = 0; i < left - 1; i++) {
        pre = pre->next;
    }

    ListNode* cur = pre->next;
    for (int i = 0; i < right - left; i++) {
        ListNode* next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }

    return dummy.next;
}

先创建一个虚拟头节点 dummy，然后找到需要反转位置的前一个节点 pre。接着进行反转操作，将节点逐个插入到 pre 节点之后，最后返回虚拟头节点的 next 即可得到反转后的链表。

关键反转操作在第二个for循环，（第一个for循环是为了寻找起始操作位置），第二个for循环每次迭代都会将当前节点的后继指针指向前一个节点，从而改变了链表中节点的指向关系，实现了反转效果。

具体解释如下：

在开始循环之前，pre 指针指向要反转区间的前一个节点，cur 指针指向要反转区间的第一个节点，next 指针指向 cur 的下一个节点。
首先，将 cur->next 指向 next->next，即将 cur 节点的后继指针指向 next 节点的后一个节点，断开了 cur 节点与 next 节点的联系。
然后，将 next->next 指向 pre->next，即将 next 节点的后继指针指向 pre 节点的后一个节点，将 next 节点插入到 pre 节点之后。
最后，更新 pre、cur 和 next 指针，使它们分别指向下一个节点，继续进行下一轮反转操作。
通过以上操作，循环不断地将当前节点的后继指针指向前一个节点，实现了链表节点的反转。最终完成循环后，pre 指针所指向的节点就是反转后的链表头节点，整个区间的节点也实现了反转。文章来源地址https://www.toymoban.com/news/detail-838625.html

到了这里，关于【C++】每日一题 92 反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！