题目描述

思路

老样子，还是先用递归试试。
在基本问题中，也就是left == rigth或者left+1 == right时，直接将两个元素调换顺序即可。
我突然发现代码随想录里好像讲过一个用双指针法反转链表的算法。
那道题是把整个链表翻转，
代码如下：

//双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
//递归法
class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

根据上面的算法得出这题的算法：
代码如下：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //先用非递归的算法写
        if(left == right ){
            return head;
        }
        if(head -> next == nullptr){
            return head;
        }

        int i = 1;
        ListNode* tmp;
        
        ListNode* righthead ;
        ListNode* lefthead;
        ListNode* cur = head;
        ListNode* Dummy = new ListNode(0, head);
        ListNode* pre = Dummy;
        while(i< left ){
            pre = pre -> next;
            i++;
        }
        cur = pre -> next;

        lefthead = pre;
        righthead = cur;
        while(cur != nullptr && i <= right){
            tmp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = tmp;
            i++;
        }
        righthead -> next = cur;
        lefthead -> next = pre;
        return Dummy -> next;
    }
};

总结

写循环出错的时候很多时候都是循环条件出了问题，这次想了好久的一个报错居然是两个while循环都忘了写循环变量自增。。
这种链表反转的处理方法很实用，以后需要反转链表的时候都可以这样写。