LeetCode刷题之路92题翻转链表Ⅱ

2020年4月17日15:24:56算法 LeetCode评论72阅读模式

前言

反转链表可以先看我这篇文章:
Leetcode 206题 反转链表(Reverse Linked List)Java语言求解文章源自随机的未知-https://sjdwz.com/11144.html

题目链接

https://leetcode-cn.com/problems/reverse-linked-list-ii/文章源自随机的未知-https://sjdwz.com/11144.html

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL文章源自随机的未知-https://sjdwz.com/11144.html

分析

给定初始链表为 1->2->3->4->5->NULL,如图文章源自随机的未知-https://sjdwz.com/11144.html

LeetCode刷题之路92题翻转链表Ⅱ
初始状态

我们需要找到第 m 个节点和第 n 个节点,分别记为 MNode 和 ** NNode** 同时也要记录第 m 个节点的前驱节点,记为 Mpre;文章源自随机的未知-https://sjdwz.com/11144.html

LeetCode刷题之路92题翻转链表Ⅱ
演示图1

我们接下来要做的是,先把Mprenext域 指向NodeM节点的后一个节点;
再把 NodeM所在节点移动到 NodeN 所在节点之后,使得 NodeNnext域指向 NodeM所在节点,NodeM所在节点 next域 指向 NodeNnext域所指节点;
然后让 NodeM指向Mprenext域 指向的节点;文章源自随机的未知-https://sjdwz.com/11144.html

LeetCode刷题之路92题翻转链表Ⅱ
演示图2

然后再重复上面的步骤;文章源自随机的未知-https://sjdwz.com/11144.html

LeetCode刷题之路92题翻转链表Ⅱ
这是 NodeMNodeN 相遇,反转完成。文章源自随机的未知-https://sjdwz.com/11144.html

代码

为了记录NodeM的前驱节点,我们新建一个虚拟节点,使得该节点的next域指向head;文章源自随机的未知-https://sjdwz.com/11144.html

ListNode pre = new ListNode(0);

我们并不移动pre这个节点,因为在移动的过程中会改变pre存储的地址,我们再新建一个Mpre文章源自随机的未知-https://sjdwz.com/11144.html

ListNode Mpre = pre;

新建变量和找NodeM节点和NodeN节点的代码为:文章源自随机的未知-https://sjdwz.com/11144.html

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++;
        }

反转的代码为:文章源自随机的未知-https://sjdwz.com/11144.html

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

因为我们新建了一个虚拟节点,我们返回如下文章源自随机的未知-https://sjdwz.com/11144.html

return pre.next;

完整代码如下:文章源自随机的未知-https://sjdwz.com/11144.html

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;
    }
}

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11144.html

扫描下方的二维码关注我的微信公众号:随机的未知文章源自随机的未知-https://sjdwz.com/11144.html

LeetCode刷题之路92题翻转链表Ⅱ
微信公众号:code随笔
文章源自随机的未知-https://sjdwz.com/11144.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年4月17日15:24:56
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11144.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定