熊二 | C++ | #牛群的重新排列#

题目考查的知识点

• 递归翻转链表
• 双指针
• 链表的断链与重连

题目解答方法的文字解析

aaaaaa->bbbbbb->ccccccc

其中“bbbbbb”是链表中需要反转的部分

1. pH和pT指针初始化为head
2. 移动pH和pT指针，使得指向要反转的链表的头节点和尾节点
3. 使用递归反转链表“bbbbbb”
4. 重新连接链表“ccccccc”

本题解析所用的编程语言

• c++

完整且正确的编程代码

/*
aaaaaa->bbbbbb->ccccccc
其中“bbbbbb”是链表中需要反转的部分
*/
class Solution {
  public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode*pH = head, *pT = head, *dummyHead=new ListNode(-1), *prev = dummyHead;
        dummyHead->next = head;
        
        right -= left;
        --left;
        while(left--){
            prev = pH;
            pH = pH->next;
        }
        pT = pH;
        while(right--){
            pT = pT->next;
        }

        ListNode*resual = pT->next;// 被翻转的链表的后半部分"ccccccc"
        pT->next = nullptr;
        prev->next = helper(pH);// 获得反转后的"bbbbbb", 并让"aaaaaa"连接上这部分
        pH->next = resual;// 连接后半部分"ccccccc"
        return dummyHead->next;
    }
    // 翻转链表
    ListNode* helper(ListNode* head) {
        if (head == nullptr || head->next == nullptr)return head;
        ListNode* ret = helper(head->next);
        ListNode* hNext = head->next;
        head->next = nullptr;
        hNext->next = head;
        return ret;
    }
};