【算法社区】链表之反转链表、删除链表的倒数第 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


相关文章
|
19天前
|
机器学习/深度学习 自然语言处理 算法
小红书:通过商品标签API自动生成内容标签,优化社区推荐算法
小红书通过商品标签API自动生成内容标签,提升推荐系统精准度与用户体验。流程包括API集成、标签生成算法与推荐优化,实现高效率、智能化内容匹配,助力社交电商发展。
51 0
|
3月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
102 0
|
6月前
|
存储 监控 算法
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
105 5
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
308 25
|
7月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
112 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
10月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
10月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表