题目描述

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

图片说明
参考:https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/

/**
 * 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) {
        ListNode* fixpre=new ListNode(0);
        fixpre->next=head;
        ListNode* guard=fixpre,*p=guard->next;//guard是要转的位置的前一个节点,p是要旋转的第一个节点
        int n=left-1;
        while(n--){//循环left-1次,找到开始旋转的位置
            guard=guard->next;
            p=guard->next;
        }
        n=right-left;
        while(n--){//循环right-left次,完成后面right-left个节点通过头插法放在guard后面
            ListNode* temp=p->next;
            p->next=temp->next;

            temp->next=guard->next;
            guard->next=temp;
        }
        return fixpre->next;//不能返回head
    }
};

```