BM2 链表内指定区间反转

Dear 丶 2023-10-04 17:36 6阅读 0赞

### 描述 ###

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

数据范围： 链表长度 0 < size \\le 10000<size≤1000，0 < m \\le n \\le size0<m≤n≤size，链表中每个节点的值满足 |val| \\le 1000∣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}

/**
     * struct ListNode {
     *	int val;
     *	struct ListNode *next;
     * };
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
        // write code here
        struct ListNode* t;
        struct ListNode* new;
        struct ListNode* mi;
        struct ListNode* pre=NULL;
        struct ListNode* pro;
        if(m==n){
            return head;
        }
        else{  //总共分为三部分：m之前的头和尾，[m,n]的逆转后的头和尾，n之后的头
            t=head;  //保存表头
            for(int j=0;j<m-1;j++){  //m大于1的时候
                pre=head;  //指向m-1的节点，m不为1
                head=head->next;
            }
            //此时head是指向m节点的
            mi=head;  //逆序后的子表尾第n个节点
            for(int i=m;i<=n;i++){
                new=head->next;
                head->next=pro;
                pro=head;  //指向逆序后的子表头
                head=new;  //指向n+1个节点
            }  
            mi->next=head;
            if(pre!=NULL)
               pre->next=pro;
            else   //如果为空，则m从第一个位置开始
                t=pro;  
            return t;
            
            
            
        }
    }