LeetCode92-反转链表II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/reverse-linked-list-ii/

中文链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目详述

  1. 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

    说明:
    1 ≤ m ≤ n ≤ 链表长度。

    示例:

    1
    2
    输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

题目详解

本题是指定反转区间来反转链表，是 LeetCode206-反转链表 的加强版。主要有四个关键的结点：

  • 左边链表的尾结点
  • 中间链表反转后的尾结点
  • 中间链表反转后的头结点
  • 右边链表的头结点。

这四个结点也就是原来位于链表 m - 1、m、n、n + 1 处的四个结点。在遍历过程中记录下这四个结点，同时反转中间链表，最后把这三个链表链接上即可。为了方便，可以新建一个头结点。

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
public class LeetCode_00092 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 得到左边链表的尾结点
        ListNode left = dummy;
        for (int i = 1; i < m; ++i) {
            left = left.next;
        }
        // 翻转
        ListNode cur = left.next;
        ListNode pre = null;
        for (int i = m; i <= n; ++i) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 此时 left.next 指向中间链表的尾结点，cur 指向右边链表的头结点
        left.next.next = cur;
        // 此时 pre 指向中间链表反转后的头结点
        left.next = pre;
        return dummy.next;
    }
}