C++实现LeetCode(92.倒置链表之二)

C++实现LeetCode(92.倒置链表之二)的完整攻略如下：

题目描述

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

解题思路

这是一道链表题目。要反转从位置left到位置right的链表节点，可以按照以下步骤进行：

1. 先找到要反转前面的那个节点pre_left，和要反转节点最后面的那个节点pos_right。
2. 记录pos_right之后的节点next_right。
3. 将链表从left到right的部分进行反转。
4. 将pre_left的next节点指向反转后的链表头节点，将反转后的链表尾节点指向next_right。

具体实现可以参考下面的代码。

代码实现

#include<iostream>
#include<vector>
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(!head || !head->next)    return head;  // 特判，如果链表为空或者只有一个节点，则返回head

        ListNode* dummy = new ListNode(-1);   // 定义一个虚拟头节点，便于处理特殊情况
        dummy->next = head; // 虚拟头节点的next指向head

        ListNode* pre_left = dummy, *pos_right = dummy; // 定义pre_left和pos_right（初始值为dummy）
        for(int i = 1; i < left; ++i)
            pre_left = pre_left->next;
        for(int i = 1; i <= right; ++i)
            pos_right = pos_right->next;

        ListNode* next_right = pos_right->next;    // 记录pos_right之后的节点
        pos_right->next = NULL; // 将pos_right之后的节点断开

        ListNode* left_node = pre_left->next; // 记录要反转节点的头节点
        ListNode* reverse_head = reverseList(pre_left->next);  // 反转left到right之间的节点
        pre_left->next = reverse_head;  // 将pre_left的next节点指向反转后的链表头节点
        left_node->next = next_right;   // 将反转后的链表尾节点指向next_right

        return dummy->next;
    }

    ListNode* reverseList(ListNode* head) {  // 反转整个链表
        if(!head || !head->next)    return head;
        ListNode* p = reverseList(head->next);   // p指向反转后的链表头结点，即原链表的尾结点
        head->next->next = head;    // 反转当前节点和下一个节点
        head->next = NULL;  // 反转后将当前节点的next置为NULL
        return p;   // 返回反转后的链表头结点
    }
};

示例说明

输入: 1->2->3->4->5->NULL, left = 2, right = 4

输出: 1->4->3->2->5->NULL

输入: 5, left = 1, right = 1

输出: 5

以上就是C++实现LeetCode(92.倒置链表之二)的完整攻略。