【力扣精选】3分钟拿下反转链表所有题型

这篇具有很好参考价值的文章主要介绍了【力扣精选】3分钟拿下反转链表所有题型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🥪 写在前面

Hello朋友们😋,我是秋刀鱼🐟,一只活跃于Java区与算法区的新人博主~

欢迎大家加入高校算法学习社区🏰: https://bbs.csdn.net/forums/Suanfa,社区里大佬云集,大家互相交流学习!

从今天开始我将陆续更新《轻松拿捏大厂面试题》专栏文章,本专栏将挑选大厂出现频率极高的面试题做专题解读,本篇也是专栏的第一篇《反转链表篇》。

🎉🎉主页:秋刀鱼与猫🎉🎉
🎉🎉期待你的支持与关注~🎉🎉


反转链表作为大厂一类高频面试题,相信可能会让很多人头疼😭,究其原因主要是对于链表结构把握不到位且没有完整梳理链表反转过程。

因此这篇博客主要分享一下我对于反转链表解题的理解,用画图的方式帮助大家理解过程,循序渐进地带领大家一步一步攻克这类难题😇

🍔 反转链表

🥗 题目描述

题目传送门🌌

【力扣精选】3分钟拿下反转链表所有题型
题目难度:⭐️⭐️
出现频率:38.38%

🌮 解题分析

开始链表反转类问题之前,先阐述一下这类题的一般解题方法:

  • 定义一个虚拟头结点,方便反转后链表头结点的返回。
  • 找到需要操作的结点位置,使用修改next的方式修改链表指向顺序达到反转的目的。

话不多说就让我们开始吧😁

为了将给定的链表反转,首先需要指定当前遍历到的结点head,其次反转链表的本质是将 head 结点指向其前一个结点,因此存储 head 结点的前驱结点为 pre。既然 head 结点反转需要指前一个结点 pre ,那修改前 head 的下一个结点就存储在 next 中,保证遍历地进行。总结一下就是:

  • head:当前遍历的结点
  • pre:head 结点的前一个结点,head为头结点时值为 null。
  • next:反转 head 结点前的下一个结点

下面先讲讲如何反转一个链表,假定反转前首先初始状态如下:

【力扣精选】3分钟拿下反转链表所有题型

遍历的结点为 head ,反转的过程实际上是修改head.next为 head 的前一个元素pre,也就是执行head.next=pre
【力扣精选】3分钟拿下反转链表所有题型
可以看到:head 结点的 next 指向已经被修改,覆盖了原来的 next 指向 , 此时就体现出 next 指针的重要性。将 pre 指向 head, head 指向其修改前的下一个元素 next ,进入下一次修改的循环:
【力扣精选】3分钟拿下反转链表所有题型
当 head 指向为 NULL 时,循环结束,此时的真正的头结点是 head 的前一个元素 pre ,因此将 pre 作为结果返回。

🧀 参考代码(Java语言)

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        // 指向 head 的前一个元素
        ListNode pre = null;
        // 循环结束的条件为 head == null
        while (head != null) {
            // 用 next 保存修改前的下一个元素位置
            ListNode next = head.next;
            // 修改
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

🍟 反转链表 II

🥗 题目描述

题目传送门🌌
【力扣精选】3分钟拿下反转链表所有题型
题目难度:⭐️⭐️⭐️
出现频率:37.36%

🌮 解题分析

题目要求:只能反转一部分链表,剩余一部分链表顺序保持不变。在尝试了半个小时的挣扎后看着臃肿的代码与不知所名的变量,秋刀鱼不禁陷入了沉思:有什么好的方法能够简单、高效地解决这一类问题呢?

片刻后灵光一现!突然想到上一题中反转链表的代码与本题都是处理链表的反转,那上题的代码或许能派上用场!

反转链表代码中传入参数是一个链表的头结点,返回的是反转后的头结点。那只需要找到反转部分的头部结点作为参数传入后,返回的不就是反转后链表的头部结点了嘛!

但如果直接传入反转头结点进入函数中,那之后所有的结点都会被反转!因此将反转部分尾与其之后结点断开是一个不错的处理方式。

因此只需要做到下面几点就能够优雅地解决这道题目:

  • 反转部分头结点: h
  • 反转部分头结点前驱结点: preH
  • 反转部分尾结点: t
  • 反转部分尾结点后继结点: afterT

反转可能出现在头结点上,这种情况下 preH 的处理会相当的困难。可以使用一个链表中常见的方法:添加一个虚拟头结点preHead的方式,使得虚拟头结点做为原来头结点head的前驱结点,那么preHead.next就是需要返回的结果。

一图胜千言,下面这张图更好地阐述了上面的构思:

【力扣精选】3分钟拿下反转链表所有题型

但仔细观察:反转之后 preH.nexth.next 指向明显出现错误,因此重新调整链表是不可缺少的一环。

根据上图不难发现:调整过程只需要将 preH.next 指向反转后的头结点 th.next 指向 afterT 就能够完成调整!
【力扣精选】3分钟拿下反转链表所有题型
当调整完成后,返回 preHead.next 即是新的头结点也是题目的答案。

🧀 参考代码(Java语言)

class Solution {
    // 上一题翻转链表的代码
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
	// 题目函数
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 虚拟头结点 preHead
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode preH, h, t, tmp, afterT;
        // 初始化
        t = afterT = preH = tmp = h = preHead;
        // 位置参数,从0开始
        int idx = 0;
        while (tmp != null) {
            // tmp 指向 preH
            if (idx == left - 1) {
                h = tmp.next;
                preH = tmp;
            }
            // tmp 指向 t
            if (idx == right) {
                t = tmp;
                afterT = tmp.next;
                // 断开不需要翻转的部分
                tmp.next = null;
                break;
            }
            tmp = tmp.next;
            ++idx;
        }
        // 等价于 preH.next = reverseList(h);
        reverseList(h);
        preH.next = t;
        //修改h.next的指向完成尾部的拼接
        h.next = afterT;
        return preHead.next;
    }
}

🍕 K个一组反转链表

🥗 题目描述

题目传送门🌌
【力扣精选】3分钟拿下反转链表所有题型
题目难度:⭐️⭐️⭐️⭐️
出现频率:39.76%

🌮 解题分析

我相信大多数的朋友第一次遇见这题都是蒙圈的状态。题目要求每 K 组进行一次链表反转,长度不够 K 组的部分保留原来顺序,这怎么办处理才好呢还真是伤脑筋。

【力扣精选】3分钟拿下反转链表所有题型

此时我们可以换换思路,用之前两道题的解题思路解决这道题目:每 K 组进行一次链表反转,是不是对应着反转 [ 1 , k ] , [ k + 1 , 2 k ] , [ 2 k + 1 , 3 k ] . . . [1,k],[k+1,2k],[2k+1,3k]... [1,k],[k+1,2k],[2k+1,3k]... 的链表元素呢,而上一题 反转链表 II 中处理的正好就是这种某段链表反转的问题!因此只需要借用上一题的代码就能够优雅地拿捏这道题。

为了方便处理首先定义一个头结点的前驱结点preHead,而每次传入 反转链表 II 参数是头结点,即传入preHead.next。定义一个计数器 idx 同时定义一个遍历链表的指针 tmp,tmp 开始时指向头结点 head ,例如下图所示。

  • 计数器 idx 记录遍历次数
  • 遍历指针 tmp 遍历链表
  • 记录反转前下一个结点 next

【力扣精选】3分钟拿下反转链表所有题型

当计数器 idx%k==0时,tmp指向需要一组的最后一个结点,此时进行 K 个一组的反转操作,反转 [ i d x − k + 1 , k ] [idx-k+1,k] [idxk+1,k] 链表结点。

【力扣精选】3分钟拿下反转链表所有题型

第一次转置会导致preHead.next指向出错,因此反转后将新的头结点赋值给 preHead.next。当 tmp 指向为空时循环结束,最终返回preHead.next即是结果。

【力扣精选】3分钟拿下反转链表所有题型

🧀 参考代码(Java语言)

class Solution {
    // 反转链表 代码
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    // 反转链表II 代码
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode preH, h, t, tmp, afterT;
        t = afterT = preH = tmp = h = preHead;
        int idx = 0;
        while (tmp != null) {
            if (idx == left - 1) {
                h = tmp.next;
                preH = tmp;
            }
            if (idx == right) {
                t = tmp;
                afterT = tmp.next;
                tmp.next = null;
                break;
            }
            tmp = tmp.next;
            ++idx;
        }
        reverseList(h);
        preH.next = t;
        h.next = afterT;
        return preHead.next;
    }
    // 题目函数
    public ListNode reverseKGroup(ListNode head, int k) {
        // preHead 声明为头结点的前驱结点
        ListNode preHead = new ListNode();
        preHead.next = head;
        // tmp 遍历链表
        ListNode tmp = head;
        int idx = 0;
        while (tmp != null) {
            ++idx;
            ListNode next = tmp.next;
            if (idx % k == 0) {
                preHead.next = reverseBetween(preHead.next, idx - k + 1, idx);
            }
            tmp = next;
        }
        return preHead.next;
    }
}

🧡 写在最后

反转链表的高频题讲解到此就结束了,其核心还是抓住推导反转的过程,一步一步完成链表的反转操作,但是细节慢慢一定要小心谨慎(秋刀鱼本人就掉过很多次坑😥),因此一定要小心。文章来源地址https://www.toymoban.com/news/detail-422612.html

✨如果觉得本篇博客还写的不错的话可以三连支持一下博主✨
【力扣精选】3分钟拿下反转链表所有题型

到了这里,关于【力扣精选】3分钟拿下反转链表所有题型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣每日一道系列 --- LeetCode 206. 反转链表

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 206. 反转链表 初始化两个指针, cur 和 newhead 。 cur 指向给定的链表头节点, newhead 初始为 NULL 。 在 cur 不为空的情况下,执行循环。 首先,记录下 cur 的下

    2024年02月04日
    浏览(39)
  • 力扣第92题——反转链表 II(C语言题解)

    给你单链表的头指针  head  和两个整数  left  和  right  ,其中  left = right  。请你反转从位置  left  到位置  right  的链表节点,返回  反转后的链表  。 示例 1: 示例 2: 提示: 链表中节点数目为  n 1 = n = 500 -500 = Node.val = 500 1 = left = right = n 我们以下图中黄色区域的链

    2024年01月23日
    浏览(48)
  • 【数据结构】--单链表力扣面试题②反转链表

    目录 题目链接:反转链表   法一:直接反转法 法二:头插法 题目分析: 创建一个新链表,然后值是逆置的行吗?不行。因为题目要求的是在 原链表上逆置,改变原链表的指向,并不是值的拷贝后的逆转 。 那其实总共有三种方法 。 法一,直接原地翻转。法二,头插法。

    2024年02月06日
    浏览(38)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(67)
  • 反转链表 Java版 图文并茂思路分析带答案(力扣第206题)

    力扣第206题 我们不只是简单的学习(背诵)一个数据结构,而是要分析他的思路,以及为什么要有不同的指针等等 思路分析:首先要链表有个头指针没有任何问题 然后,我们要将1的下一个节点指向空,这样才能将其反转过来,但是这个时候我们发现和下一个节点2失去了联

    2024年02月05日
    浏览(43)
  • 力扣---二叉树OJ题(多种题型二叉树)

    👧 个人主页 :@小沈熬夜秃头中୧⍤⃝❅ 😚 小编介绍 :欢迎来到我的乱七八糟小星球🌝 📋 专栏 :力扣—LeetCode刷题 🔑 本章内容 :力扣—二叉树OJ题 送给各位 💌:活着就意味着要必须做点什么 请好好努力 欢迎 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇

    2024年02月07日
    浏览(42)
  • 30天拿下Rust之所有权

    概述         在编程语言的世界中,Rust凭借其独特的所有权机制脱颖而出,为开发者提供了一种新颖而强大的工具来防止内存错误。这一特性不仅确保了代码的安全性,还极大地提升了程序的性能。在Rust中,所有权是一种编译时检查机制,用于追踪哪些内存或资源何时可

    2024年03月08日
    浏览(40)
  • 【LeetCode】每日一题:链表部分经典题型

    ​👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 归纳链表部分经典题型 。 206.反转链表 、 876.链表的中间节点 、 21.合并两个有序链表 、 160.相交链表 、 141.环形链表 、 142.环形链表Ⅱ 🐼本文作者:花 碟 🐸发布时间:2023.5.17 👉 206.反转链表 题目描述:给你单链表的头

    2024年02月05日
    浏览(39)
  • 【数据结构】链表经典OJ题,常见几类题型(二)

    看到这类题型首先要判断链表是否相交,而相交条件: 两链尾部节点相同(地址相同, val 值相同, next 相同) 。这样我们便可 找到两链表的尾节点并判断这两个节点地址是否相同 ,若相同则两链表相交。上面这种情况两链表呈 \\\'Y\\\' 型,那么我们想一下两链表相交是否可以

    2024年02月05日
    浏览(46)
  • 文心大模型3.5国际评测拿下7个满分,大二学生1分钟AI作画估值百万!

    近日,广州美术学院的一名大二学生肖遥参加了一场AI创作大赛,她以兵马俑为创作来源,通过AI作画平台文心一格设计的一套《赛博朋克兵马俑》潮玩盲盒,从确定创意到画作实现,只花了不到1分钟时间,却被专家评估市场价值超百万。 有评论分析,大模型是这一轮AIGC发展

    2024年02月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包