【每日一练】图解：链表内指定区间反转

题目：反转链表

题目来源牛客 - 链接在此

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

示例

初始代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

思路

这道题难度为中等，但是因为如果写过单链表反转，那么这道题其实并不难。

（还不会单链表反转的同学戳这里）

对比这一题和单链表反转，无非一个的反转整个链表，一个是局部反转，那么我们只需要把局部看做一个整体来进行反转，然后再对“整体”的头尾的指向进行处理即可。

第一步：处理特殊情况

if (head == null || m == n) return head;
1

第二步：
使用一个函数来实现链表的反转，参数为反转起始节点 start 和 反转结束节点end。

reverseBetweenSE(head,end);
1

图解如下：

函数实现如图：

第三步：end的next已经成为start的next，接下来要处理start前面的指向。

图解如下：

到这里整个题目就很清楚啦！
下面直接上代码~~

完整代码：

/**
     * 链表内指定区间反转
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
                                                                                                                                
        //找到反转结束节点
        ListNode end = head;
        for (int i = 1; i < n; i++) {
            end = end.next;
        }
        //根据反转起始节点是否为头结点分情况处理
        if (m == 1) {
            reverseBetweenSE(head,end);
            head = end;
        } else {
            ListNode preStart = head;
            for (int i = 1; i < m - 1; i++) {
                preStart = preStart.next;
            }
            reverseBetweenSE(preStart.next,end);
            preStart.next = end;
        }
        return head;
    }

    /*
    给定头尾节点，反转链表
     */
    private void reverseBetweenSE(ListNode start, ListNode end) {
        ListNode cur = start.next;
        start.next = end.next;
        while (cur != end) {
            ListNode CurNext = cur.next;
            cur.next = start;
            start = cur;
            cur = CurNext;
        }
        cur.next = start;
    }
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

关注我！一起加入每日一练吧！~