题目描述

请将链表中第 m个节点和第 n 个节点之间的部分翻转。
链表最多只能遍历一遍。

注意：1≤m≤n≤1≤m≤n≤ 链表长度。

样例

输入：1->2->3->4->5->NULL, m = 2, n = 4
输出：1->4->3->2->5->NULL

算法

根据题目要求 只能遍历一边，因此考虑边遍历边前插的方法

具体就是：

1->2->3->4->5 按照题目 在2号位置前面插上3 变成了1->3->2->4->5,
其中2号（也就是m号位置的前一个位置）存下来 每次往后遍历一个就插一个
至于边界问题，我是调试出来的，不外乎 + - 1 的问题

时间复杂度 O（N）

C++ 代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new  ListNode(-1);//转行的小白第一次听课接触到这个虚拟头结点方法
        ListNode* tmp=dummy;
        dummy->next=head;//虚拟头结点跟给定的链表联系起来
        for(int i=0;i<left-1;i++){
            tmp=tmp->next;
        }
        head=tmp->next;//指定left 前一个节点的位置
        for(int i=left;i<right;i++){
            ListNode* helper= head->next;
            head->next=helper->next;
            helper->next=tmp->next;
            tmp->next=helper;
        }
        return dummy->next;

    }
};