博客

92. 反转链表 II （重要的修改链表的结点指向方式，画图！！！！）

链接：

Leetcode 92. 反转链表 II

解题思路

利用头插法，每一趟都是将nex改为区间列表内的头节点，因为是使用的循环结构，所以区间列表就是cur-nex的这个区间中的链表（最重要的就是维护三个节点：pre，cur，nex）。注意：cur是尾，nex是头，pre的头的前面一个节点。

迭代过程：（一定要自己在草稿纸上面画图）

1. nex=cur->next;刚开始nex是未反转（即将反转）链表的后面一个节点
   
   cur->next=nex->next;cur是尾节点，所以要将他改成指向cur-nex区间外的头节点。

2. nex=cur->next;刚开始nex是未反转（即将反转）链表的后面一个节点
   
   cur->next=nex->next;cur是尾节点，所以要将他改成指向cur-nex区间外的头节点。

3. nex->next=pre->next;这个时候nex就是头节点了（体现头插法）。

4. pre->next=nex;pre是外部前面的一个联系，指向cur-nex区间的头。

注意：

顺序不可以改变

，我最开始没有处理好就是因为3和4过程顺序搞反了。

代码

/**
 * 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* dummy= new ListNode(-1, head);
        ListNode* pre=dummy, *cur, *nex;
        for(int i=0; i<left-1; i++){
            pre=pre->next;
        }
        cur=pre->next;
        for(int j=0; j<right-left; j++){
            nex=cur->next;
            cur->next=nex->next;
            nex->next=pre->next;
            pre->next=nex;
            // nex=cur->next;
            // cur=nex;
        }
        return dummy->next;
    }
};