牛客网刷题-链表内指定区间反转_将一个链表 位置到 位置之间的区间反转,要求时间复杂度 ,空间复杂度 。

问题描述

将一个链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 ，空间复杂度 。
例如：
给出的链表为1→2→3→4→5→NULL
返回 1→4→3→2→5→NULL
注意：
给出的 满足以下条件：
链表长度1≤m≤n≤链表长度

示例

示例1

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

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

解决思路

思路

1. 根据m大小，先确认前置节点；倒置m-n区间的节点。
   这里主要是一些节点的互相指，容易乱，这里通过一个图展示了两个节点互换的过程。
   

代码实现

// 思路1
public class Solution {  
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if(head == null) return null;
        ListNode res = new ListNode(-1);
        res.next = head; // -1->1->2->3->4->5
        ListNode pre = res; //备份指针
        //移动指针，找到m之前的位置
        for(int i = 1; i<m; i++){
            pre = pre.next; //指向1
        }
        //创建当前指针
        ListNode cur = pre.next; //指向2
        //反转链表，从m这个位置开始到n
        for(int i = m; i < n; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度分析：
O(N)：n为第二个位置

空间复杂度分析：
O(1)：没有使用额外的空间

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

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