自我总结：Leetcode 92. 反转链表II

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

提示：链表中节点数为n，1<=n<=500，-500<=Node.val<=500，1<=left<=right<=n

介绍方法：穿针引线大法

用处：翻转链表

借用一下题解的图，侵权删

1. 先在最前面加一个dummy node, dummy->next = head;

2. 建立三个node, pre, cur, next。 pre是指向待转换区域的前一个，cur只初始化一次，是原链表的pre的后一个，也是第一个待翻转的node。cur以后一直不换地方！！！next每次要更新，在更新时永远指向cur的后一个node。

3. 先找好pre的位置，并且初始化pre, cur，声明next

4. 写好循环条件，一直做上图的①②③。零是next = cur->next; ①是cur->next = next->next; ②是next->next = pre->next; ③是pre->next = next;

5. 返回dummy->next

例子代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        dummy->next = head;
        for(int i = 0;inext;
        }
        ListNode* cur = pre->next;
        ListNode* next;
        for(int j = left; jnext;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;   
        }
        return dummy->next;
    }
};

注意 ：这里的第一个循环的left的定义范围是1开始，所以 i

这样只需遍历一次链表就能翻转链表了

时间复杂度：O(N)

空间复杂度：O(1)