【Leetcode】92.反转链表 II

92 反转链表 II

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

说明:
$1 ≤ m ≤ n ≤$链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路：

  1. 我们定义两个指针，分别称之为cur和pre。我们首先根据方法的参数m确定cur和pre的位置。将pre移动到第一个要反转的节点的前面，将cur移动到第一个要反转的节点的位置上

  2. 将cur后面的元素删除，然后添加到pre的后面。也即头插法。

  3. 根据m和n重复步骤2

注意:
不能依赖头节点作pre，头节点的下一个节点做cur。这样的话当m=1时即第一个节点也要参与反转时就不适用了。于是建立一个在head前面的节点，并将它和链表联系起来，在通过它将pre和cur初始化

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode reverseBetween(ListNode head, int m, int n) {
    //新建一个节点，并将这个节点和原有链表联系起来
    ListNode preHeadNode = new ListNode(0);
    preHeadNode.next = head;
    //新建并初始化两个指针
    ListNode pre = preHeadNode;
    ListNode cur = preHeadNode.next;
    //移动这两个指针，直到cur指向要反转的第一个节点，pre指向它的前面
    for(int i = 0; i < m - 1; i++){
        cur = cur.next;
        pre = pre.next;
    }
    //
    for(int i = 0; i < m - n;i++){
        //先拿到要删除（即要插入）的节点
        ListNode remove = cur.next;
        //经过下面这步，跳过了cur的下一个节点。达到了把这个节点删除的效果
        cur.next = cur.next.next;
        //接下来是插入操作
        remove.next = pre.next;
        pre.next = remove;
    }
    return preHeadNode.next;
}