【链表】反转指定区间的链表_链表内指定区间反转

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 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(1)

思路

反转给定区间的链表，需要首先定位到指定的区间，然后在切断区间前后的节点，然后对指定区间的链表进行反转，反转后在与之前切段的节点连接。

注意：链表的实现Java对象，是一种引用类型，所以在对链表进行操作时，需要考虑引用类型的特殊性，变量通过指针指向对象的地址。

实现

public static ListNode reverseBetween (ListNode head, int m, int n) {
        // 如果m=n,直接返回
        if(m==n){
            return head;
        }
        // 建立一个虚拟节点，防止m=1时，没有前节点的问题
        ListNode weekNode=new ListNode(-1);
        weekNode.next=head;
        // 需要定位到需要反转的链表区间，而且还需要保存反转区间前后的节点信息
        // 定义一个节点，保存反转区间前一个节点的信息
        ListNode pre=weekNode;
        // pre节点的位置需要根据m来获取,例如m=2,那么pre应该从虚拟节点往后移动一个节点，所以pre的位置需要移动m-1个节点
        for (int i = 0; i < m - 1; i++) {
            pre=pre.next;
        }
        // 定义一个左指针指向反转区间的第一个节点
        ListNode left=pre.next;
        // 定一个右指针指向反转区间的最后一个节点
        ListNode right=pre;
        // 右指针的位置需要根据m以及n的值来计算移动，移动的个数n-m+1，也就是pre节点开始移动要反转区间的长度
        for (int i = 0; i < n - m + 1; i++) {
            right=right.next;
        }
        // 定一个节点，来指向反转区间后面的节点
        ListNode last=right.next;
        // 现在left，right指针已经标记出要反转的链表，接下来需要断开与前后节点的连接了
        pre.next=null;
        right.next=null;
        // 此时，left指针所指的链表就是要进行反转的链表，进行链表的反转
        reverseNode(left);
        // 反转过后，right指针指向的节点为反转之后的节点。明白这一点很重要
        // 反转之前left指针指向反转链表的头节点，反转之后，头节点就变成right指针指向的节点了，这也是反转的意义
        // 连接之前断掉的节点
        pre.next=right;
        left.next=last;
        // 因为weeknode是我们添加的虚拟节点，所以需要返回其next
        return  weekNode.next;
    }

    private static void reverseNode(ListNode head){
        // 2->3->4
        // 需要两个指针，分别指向前后两个节点
        // pre代表当前节点的前一个节点，所以初始值为null
        ListNode pre=null;
        // cur 指向当前第一个节点
        ListNode cur=head;
        while (cur!=null){
            // 获取当前节点的下一个节点
            ListNode next=cur.next;
            // 当前节点指向前一个节点
            cur.next=pre;
            // pre 往后移动一个节点
            pre=cur;
            // cur节点往后移动一个节点
            cur=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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58