【BM2 链表内指定区间反转】

链表内指定区间反转

题目来源

牛客网：链表内指定区间反转

题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL,m=2,n=4,
返回 1→4→3→2→5→NULL.

数据范围： 链表长度 0 <size≤1000，0 < m≤n≤size，链表中每个节点的值满足∣val∣≤1000
要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)

示例1

输入

{1,2,3,4,5},2,4

返回值

{1,4,3,2,5}

示例2

输入

{5},1,1

输出

{5}

思路分析

• 定义一个虚拟的头节点，防止链表的头节点也被逆置
• 找到要反转的区间的起始位置及其前驱节点
• 从起始位置按单链表逆置的方法进行逆置
• 将逆置的部分与原链表进行拼接
• 返回虚拟的头结点的下一个节点

代码展示

ListNode* reverseBetween(ListNode* head, int m, int n) {
    
    if (head == NULL)
    {
    
        return NULL;
    }
    //头节点也有可能会被反转，定义一个虚拟的头节点
    ListNode* myhead = new ListNode(0);//申请新节点
    myhead->next = head;//新节点与原来的头节点连接
    ListNode* cur = myhead;

    for (int i = 0; i < m - 1; i++)
    {
    
        cur = cur->next;
    }
    ListNode* prev = cur;//开始反转点的前一个节点
    ListNode* start = prev->next;//开始反转的节点

    cur = start->next;
    ListNode* before = start;
    ListNode* next = nullptr;
    while (m < n)
    {
    
        next = cur->next;
        cur->next = before;
        before = cur;
        cur = next;
        m++;
    }
    prev->next = before;//prev的next指向反转后的起点
    start->next = cur;//start反转后成为end,所以start的next指向原来结尾的下一个节点
    return myhead->next;
}
};