【算法社区】链表之反转链表、删除链表的倒数第 N 个结点

简介: 字节跳动企业题库,链表系列,那我们从出题频率最高刷到最低,题目有206. 反转链表 、19. 删除链表的倒数第 N 个结点

image.png

前言:📫 作者简介:小明java问道之路,专注于研究计算机底层,就职于金融公司后端高级工程师,擅长交易领域的高安全/可用/并发/性能的设计和架构📫

🏆 Java领域优质创作者、阿里云专家博主、华为云享专家🏆

🔥 如果此文还不错的话,还请👍关注点赞收藏三连支持👍一下博主哦

本文导读

字节跳动企业题库,链表系列,因为有leetcode会员能看到企业出题频率,那我们从出题频率最高刷到最低,题目有206. 反转链表 、19. 删除链表的倒数第 N 个结点


206. 反转链表

【简单】【题目描述】给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]

示例 2:输入:head = [1,2] 输出:[2,1]

示例 3:输入:head = [] 输出:[]

这道题是一到老生常谈的题目,对于熟悉链表的同学来说是秒杀的,我们分递归和迭代两种方法解题

【迭代、递归】图解:

image.png

代码详解,逐行注释:

public ListNode reverseList(ListNode head) {  /*迭代法*/
        ListNode prev = null;  // 1 对于上图解析,先设置两个结点
        ListNode curr = head;  // 2
        while (curr != null) { 
            ListNode next = curr.next;  // 3 反转
            curr.next = prev;           // 4
            prev = curr;   // 5 向前移动
            curr = next;   // 6
        }
        return prev;
    }
    public ListNode reverseList(ListNode head) {  /*递归法*/
        if (head == null || head.next == null) { // 递归停止条件
            return head;
        }
        ListNode newHead = reverseList(head.next); // 递归
        head.next.next = head;  // 1 将后一位指向前一位
        head.next = null;       // 2 断开前一位的next指针
        return newHead;
    }

image.gif

 

19. 删除链表的倒数第 N 个结点

【中等】【题目描述】给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

示例 1:输入:head = [1,2,3,4,5], n = 2输出:[1,2,3,5]

示例 2:输入:head = [1], n = 1输出:[]

示例 3:输入:head = [1,2], n = 1输出:[1]

这是所有大厂爱考的链表题目之一,对于熟悉链表的同学来说是秒杀的,我们用暴力法、快慢指针(双指针)法解题

image.png

代码详解,逐行注释:

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);    // 保留的头节点
        int length = getLength(head);  // 获取链表长度
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) { // 遍历到 L-n+1的位置
            cur = cur.next;
        }
        cur.next = cur.next.next;   // 删除节点
        ListNode ans = dummy.next;  // 返回保留的头节点
        return ans;
    }
    public int getLength(ListNode head) { /*遍历一遍,计算链表长度*/
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);  // 保留的头节点
        ListNode first = head;      // 快指针
        ListNode second = dummy;    // 慢指针
        for (int i = 0; i < n; ++i) // 快指针先走的n的位置
            first = first.next;
        while (first != null) {     // 同时向后移动
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next; // 删除节点
        ListNode ans = dummy.next;      // 返回保留的头节点
        return ans;
    }

image.gif


相关文章
|
25天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
26天前
|
存储 算法 搜索推荐
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
14 1
|
1月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
1月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
1月前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
49 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
32 0
|
1月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
下一篇
无影云桌面