精选力扣500题第14题 LeetCode 92. 反转链表 II【c++详细题解】

ゝ一世哀愁。 2021-07-24 12:41 400阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

**示例 1：**

![df90930509371c826efc0936085a7631.png][]

输入：head = [1,2,3,4,5], left = 2, right = 4
    输出：[1,4,3,2,5]

**示例 2：**

输入：head = [5], left = 1, right = 1
    输出：[5]

**提示：**

*  链表中节点数目为 `n`
 *  `1 <= n <= 500`
 *  `-500 <= Node.val <= 500`
 *  `1 <= left <= right <= n`

### 2、思路 ###

![88284578c04f51e263099f0e21095435.png][]

具体操作，如图所示，黑色表示当前原始状况，红色表示操作状况

*  1、添加虚拟头节点`dummy`，然后遍历链表找到第`left-1`个节点，将`a`指针指向第`left-1`个节点,`b`指针指向第`left`个节点，`c`指针指向第`left+1`个节点。
 *  2、翻转`left`到`right`的序列，即蓝色矩阵中的序列。翻转完后，`b`指向第`right`节点，`c`指向第`right+1`节点，即红色`b`,`c`字母的位置。
 *  3、先将`a->next->next`指向`c`节点，然后`a->nxet`指向`b`节点。
 *  4、最后返回虚拟头结点的下一个节点`dummy->next`

### 3、代码 ###

/** * 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 { 
    public:
        ListNode* reverseBetween(ListNode* head, int left, int right) { 
            if(left == right) return head;
            auto dummy = new ListNode(-1);//虚拟头节点
            dummy->next = head;
            auto p = dummy;
            for(int i = 0; i < left - 1; i++)  //让p走到left的前一个节点
            { 
                p = p->next;
            }
            auto a = p, b = a->next,c = b->next ;
            for(int i = left + 1; i <= right ; i++) 
            { 
                auto next = c->next;
                c->next = b;
                b = c,c = next;
            }
            a->next->next = c;
            a->next = b;
            return dummy->next;
        }
    };

**原题链接：** [92. 反转链表 II][92. _ II]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[df90930509371c826efc0936085a7631.png]: /images/20210724/acafeecf8cd6410d8c64b67e3ff6faaf.png
[88284578c04f51e263099f0e21095435.png]: /images/20210724/1e6bde8ed94548e8b0c9c597c62262ca.png
[92. _ II]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/48c115e2331c40ff9272b15929f11512.png