社区首页 >专栏 >Leetcode 92题反转链表 II（Reverse Linked List II）

Leetcode 92题反转链表 II（Reverse Linked List II）

code随笔

发布于 2020-04-22 07:43:01

40400

代码可运行

文章被收录于专栏：code随笔的专栏code随笔的专栏

运行总次数：0

代码可运行

前言

反转链表可以先看这篇文章： LeetCode 206题反转链表（Reverse Linked List）

题目链接

https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

分析

给定初始链表为 1->2->3->4->5->NULL,如图

初始状态

我们需要找到第 m 个节点和第 n 个节点，分别记为 MNode 和 ** NNode** 同时也要记录第 m 个节点的前驱节点，记为 Mpre;

演示图1

我们接下来要做的是，先把Mpre的 next域 指向NodeM节点的后一个节点；再把 NodeM所在节点移动到 NodeN 所在节点之后，使得 NodeN的 next域指向 NodeM所在节点，NodeM所在节点 next域 指向 NodeN的next域所指节点；然后让 NodeM指向Mpre的 next域 指向的节点；

演示图2

然后再重复上面的步骤；

这是 NodeM 和 NodeN 相遇，反转完成。

代码

为了记录NodeM的前驱节点，我们新建一个虚拟节点，使得该节点的next域指向head；

ListNode pre = new ListNode(0);

我们并不移动pre这个节点，因为在移动的过程中会改变pre存储的地址，我们再新建一个Mpre；

ListNode Mpre = pre;

新建变量和找NodeM节点和NodeN节点的代码为:

ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode Mpre = pre;
        ListNode NodeM = head;
        ListNode NodeN = head;
        int mNum = 1;
        int nNum = 1;
        while(mNum < m && NodeM != null){
            Mpre = NodeM;
            NodeM = NodeM.next;
            mNum++;
        }

        while(nNum < n && NodeN != null){
            NodeN = NodeN.next;
            nNum++;
        }

反转的代码为:

while(NodeM != NodeN){
  Mpre.next = NodeM.next;
        NodeM.next = NodeN.next;
        NodeN.next = NodeM;
        NodeM = Mpre.next;
}

因为我们新建了一个虚拟节点，我们返回如下

return pre.next;

完整代码如下:

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n){
        if(m==n || head == null||head.next == null){
            return head;
        }

        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode Mpre = pre;
        ListNode NodeM = head;
        ListNode NodeN = head;
        int mNum = 1;
        int nNum = 1;
        while(mNum < m && NodeM != null){
            Mpre = NodeM;
            NodeM = NodeM.next;
            mNum++;
        }

        while(nNum < n && NodeN != null){
            NodeN = NodeN.next;
            nNum++;
        }

        while(NodeM != NodeN){
            Mpre.next = NodeM.next;
            NodeM.next = NodeN.next;
            NodeN.next = NodeM;
            NodeM = Mpre.next;
        }
        return pre.next;
    }
}