你所不知道的C语言——链表

2023-05-16

linus嘴里的good taste

在一次TED演讲中,林老大在14分钟提到,代码的品味。The mind behind linux
说实话,这是我第一次听到林老大的声线。
看下边一段代码:

void remove_list_node(List *list, Node *target)
{
    Node *prev = NULL;
    Node *current = list->head;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

删除链表对应节点,用了10行。
而且需要处理当删除的目标节点是 head节点 的特殊情况。
改进:

void remove_list_node(List *list, Node *target)
{
    Node **indirect = &list->head;
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

使用了二级指针,就不需要考虑删除head节点的特殊情况了。骚的一。
 
 

合并2个有序链表

这是力扣的题的地址。21.合并2个有序链表

先看最原始写法

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    struct ListNode *ptr = head;
    while (L1 && L2) {
        if (L1->val < L2->val) {
            ptr->next = L1;
            L1 = L1->next;
        } else {
            ptr->next = L2;
            L2 = L2->next;
        }
        ptr = ptr->next;
    }
    ptr->next = L1 ? L1 : L2;
    return head->next;
}

运用上述indirect二级指针的技巧,
不需要分配一个临时的节点了:

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2) { 
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

上边的代码,需要判断是哪个节点的值更小,接到head新链表之后;
之后再把这个节点所在的链表(L1或者L2)往后推一个节点。
可以使用一个二级指针,间接指代值更小的节点,然后将它所在的链表往后推。
再次使用了一下indirect指针,见代码:

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

 
 

合并K个升序链表

也是力扣的题,23,合并K个升序链表
这一节不再考虑合并两个链表的问题,直接使用上边的合并操作。
但是这里需要考虑的是,怎么去做两两合并,最后合并成一个链表。
最笨的办法是,所有的链表都往第一条链表上合并。

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (listsSize == 0) return NULL;
    for (int i = 1; i < listsSize; i++)
        lists[0] = mergeTwoLists(lists[0], lists[i]);
    return lists[0];
}

这样第一条链表会越来越长,导致遍历一次需要的时间越来越长。
图样图森破。
来看分段合并,如图:
在这里插入图片描述
这里要考虑的是间隔interval的取值,
两两比较时,使用链表i链表i+interval
下一次比较时,是链表i+2*interval链表i+2*interval+interval…终点是i+interval < 链表的条数
interval的增长是2倍的interval增长,终点是。。。

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (listsSize == 0) return NULL;
    
    for (int interval = 1; interval < listsSize; interval *= 2) 
        for (int i = 0; i + interval < listsSize; i += interval * 2)
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    
    return lists[0];
}

这两者在力扣里面,执行时间第一个是300ms左右,第二个是个位数毫秒。
 
 

删除链表中间节点

力扣题2095
先不考虑释放这个动作,可以用一个快慢指针的方法找到中间节点。

struct ListNode *deleteMiddle(struct ListNode *head) {
    struct ListNode **indir = &head;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) 
        indir = &(*indir)->next;
    *indir = (*indir)->next;
    return head;
}

现在要删除这个中间节点了,
我们要用一个prev指针来跟随indirect指针,来准备free操作。

struct ListNode *deleteMiddle(struct ListNode *head) {
    if (!head->next) return NULL;
    
    struct ListNode **indir = &head, *prev = NULL;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
        prev = *indir;
        indir = &(*indir)->next;
    }
    prev->next = (*indir)->next;
    free(*indir);
    return head;
}

注:prev是一个一级指针。
这个写法会报错,heap_use_after_free
比如 [1, 3, 4, 7, 1, 2, 6] 链表
最终indirect指向内容为7的节点,简称 7node
prev指向 4node
free节点之前,prev->next = (*indir)->next 等同于 (*indir) = (*indir)->next
最后free的是 1node 你敢信?所以才会报错。
 

修正问题的方法:

struct ListNode *deleteMiddle(struct ListNode *head) {
    if (!head->next) return NULL;
    
    struct ListNode **indir = &head, *prev = NULL;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
        prev = *indir;
        indir = &(*indir)->next;
    }
    struct ListNode *next = (*indir)->next;
    free(*indir);
    prev->next = next; // *indir = next
    return head;
}

又搞了一个 next指针
太啰嗦了,继续简化:

struct ListNode *deleteMiddle(struct ListNode *head) {
    struct ListNode **indir = &head;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next)
        indir = &(*indir)->next;
    struct ListNode *del = *indir;
    *indir = (*indir)->next;
    free(del);
    return head;
}

 
 

完。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

你所不知道的C语言——链表 的相关文章

  • summary1 如何在Python中创建基本的ROS节点[AI]

    本课程结束时 xff0c 您将能够 xff1a 1 在模拟中 xff0c 使用ROS控制TurtleBot3机器人 2 使用roslaunch和rosrun启动ROS应用程序 3 使用关键ROS命令行工具询问正在运行的ROS应用程序 4 创
  • switch case语句用法

    一般情况下 xff0c 判断语句常用的有if else xff0c 三目运算符 xff0c 还有switch case等 xff0c 根据不同需求使用其判断语句 下面以简单示例展示 xff1a 在输入框中输入数字 xff0c 判断其星期几
  • 四轴飞行器基础

    原文知识来自果壳网 四轴飞行器基础篇 xff0c 进行一些适量增删 基本原理与名词解释 1 遥控器篇 通道 通道就是可以遥控器控制的动作路数 xff0c 比如遥控器只能控制四轴上下飞 xff0c 那么就是1个通道 但四轴在控制过程中需要控制
  • OPENWRT,爱快等软路由推荐

    这种用于路由器的开源固件 操作系统可以让它获得大多数路由器所不具备的功能 xff0c 甚至可以把一台旧PC变成强大的路由器或防火墙设备 软路由提供的一些特性和功能包括带宽监控 VLAN支持 高级无线设置 VPN集成 高级安全等等 在这篇文章
  • freeRTOS 时间管理

    1 相对时间延时 br vTaskDelay gt prvAddCurrentTaskToDelayedList 函数分析之后 xff0c 有步骤解析 br 为什么使用两个延时列表 xff1f br br br 2 绝对时间延时 br Pr
  • 美团笔试题_20220409

    前言 笔试一共五道编程题 xff08 四 43 一 xff09 xff0c 一为专项编程题 xff0c 估计不同岗位有题目不一样 xff0c 使用的是赛码网 xff0c 允许跳出界面使用自己的IDE 在此感谢筱羊冰冰提供的部分题目及题解 题
  • 最简单的socket 与物流网的传感器交换数据

    做个笔记 最简单的socket 要与物流网的传感器交换数据 登录分为用户登录 与 设备登录 1 用户登录 xff08 SSLSOCKET xff09 M login ID xx1 K xx2 n json格式 最简单的SSLSocket 基
  • 如何开发出成功的硬件产品,一个产品由概念的产生到产品的落地量产又需要经历哪些流程呢?

    对于一个硬件产品而言 xff0c 大批量的生产交付才能实现其最大的商业价值 然而 xff0c 不同于软件产品的复制升级 xff0c 硬件产品大批量生产背后所涉及的生产制造 工艺测试 品质功能 可靠性 成本等等一系列问题 xff0c 都是一个
  • 进程切换与线程切换的区别

    一 虚拟内存知识复习 虚拟内存是操作系统为每个进程提供的一种抽象 xff0c 每个进程都有属于自己的 私有的 地址连续的虚拟内存 xff0c 当然我们知道最终进程的数据及代码必然要放到物理内存上 xff0c 那么必须有某种机制能记住虚拟地址
  • eclipse-tomcat解决java.lang.OutOfMemoryError: PermGen space

    在eclipse中使用tomcat启动项目的时候 遇到问题 xff0c 报错 xff1a java lang OutOfMemoryError PermGen space 原因很简单 内存溢出 xff0c 解决方法 1 双击红色部分 2 单
  • JavaWeb项目中加入redis缓存

    关于redis缓存的优缺点不再多做结束 xff0c 请自行上网查询 1 下载 xff1a windows版本资源我已经上传 xff0c 链接 xff1a http download csdn net detail kkkder 963718
  • java 格式化时间

    public static void main String args System out println System currentTimeMillis SimpleDateFormat formatter 61 new Simple
  • linux docker删除镜像

    springcloud参考指南下载 xff1a http download csdn net download kkkder 10035750 之前的没有接触的docker xff0c 找了些文档 xff0c 按部就班的在linux下安装部
  • springboot activiti工作流简单示例

    最近一直研究springboot xff0c 根据工作需求 xff0c 工作流需要作为一个单独的微服务工程来提供给其他服务调用 xff0c 现在简单的写下工作流 xff08 使用的activiti xff09 微服务的搭建与简单使用 jdk
  • Error parsing lifecycle processing instructions pom.xml /xxxxx Maven Project Build Life

    本机是windows7 64bit xff0c eclipse版本信息 xff1a Eclipse Java EE IDE for Web Developers Version Neon 3 Release 4 6 3 Build id 2
  • freeRTOS 信号量:二值 计数 互斥 递归互斥

    用于信号量的队列 xff0c 都是只有队列数据结构的空间 xff0c 没有队列项存储空间的队列 二值 计数 互斥 递归互斥 xff0c 创建完成之后的内存状态 xff1a 转自 http blog csdn net zhzht1986101
  • Mapped Statements collection does not contain value for xxx

    说个同事出现的问题 xff1a Mapped Statements collection does not contain value for xxx 当时第一反应 xff0c 就是sql文件中没有定义id为 xxx xff0c 查看sql
  • CentOS mysql 安装

    1 因个人需要 安装了JDK https blog csdn net kkkder article details 78349419 2 下载https dev mysql com downloads mysql 5 7 html down

随机推荐

  • Spring AOP 日志记录

    package com config import java util Date AOP 添加访问日志 import org aspectj lang JoinPoint import org aspectj lang annotation
  • linux redis安装

    1 CentOS7 联网 2 进入redis官网 https redis io download 3 官网有详细教程 在执行make命令时 xff0c 报错 xff1a echo 34 34 gt make ldflags MAKE hir
  • 无人机巡线(1)

    本程序完成2020年电赛试题主要内容 如果用户认为已经掌握该文件使用方法 xff0c 请删除此文件 xff0c 然后添加FollowLine c文件 1 拿到了绿色的数据 xff1b 2 include 34 FollowLine h 34
  • 相机内参数和外参数

    求解相机内参 xff1a 相机标定 求解相机外参 xff1a 相机位姿估计 相机内参数是与相机自身特性相关的参数 xff0c 比如相机的焦距 像素大小等 xff1b 相机外参数是在世界坐标系中的参数 xff0c 比如相机的位置 旋转方向等
  • openrave安装

    需要用到某篇论文的代码 xff0c 需要用到openrave等第三方库 xff0c 折腾一番后记录一下 参考安装 https scaron info teaching installing openrave on ubuntu 14 04
  • IoT 技术演进:揭秘无源零功耗物联网通信技术原理和总体架构

    近日 xff0c OPPO发布了 零功耗通信 报告 xff0c 揭秘零功耗通信的概念 技术原理和总体架构 关键技术和挑战 xff0c 以及与6G关键技术的融合 自供电 黑科技 xff0c 零功耗通信 零功耗设备主要结合射频能量采集技术 反向
  • 解决修改httpd配置文件Options Indexes FollowSymLinks仍然无法禁止访问网站目录

    由于一些特殊需求或者安全考虑 xff0c 需要禁止用户访问网站目录 xff0c 所以需要改httpd conf配置文件 一般来说 xff0c 命令如下 xff1a vim etc httpd conf httpd conf 找到目录标签下的
  • 操作系统学习(十六) 、任务管理

    操作系统学习 xff08 十六 xff09 任务管理 一 任务 任务是处理器可以分配调度 执行和挂起的一个工作单元 它可用于执行程序 任务或进程 操作系统服务 中断或异常处理过程和内核代码 80x86提供了一种机制 xff0c 这种机制可以
  • 密码攻击——无分支的代码,执行时间是常量

    基于时间的密码攻击 考虑下边的代码 span class token keyword int span span class token function memcmp span span class token punctuation s
  • 从Simulink到PX4——Simulink-PX4插件安装与环境搭建

    从Simulink到PX4 Simulink PX4插件安装与环境搭建 前言0 准备工作1 安装WSL2 Setting up the PX4 Toolchain on Windows3 Setting up the PX4 Tool Ch
  • nuc980 linux 控制 gpio 引脚电平

    这里使用miscdevice设备的方式编写 xff0c 关键结构体与API define MISC DYNAMIC MINOR 255 struct miscdevice int minor const char name const st
  • CCM-SLAM跑自己的USB摄像头

    CCM SLAM跑自己的USB摄像头 ccm slam readme md如何使用自己的数据参数功能 尝试调用usb摄像头修改摄像头启动文件 96 usb cam test launch 96 测试摄像头修改 96 Client0 euro
  • ORB2单目读代码笔记12--单目初始化中基础矩阵推导计算、根据得分确定最佳单应矩阵和基础矩阵

    单目初始化中基础矩阵推导计算 根据得分确定最佳单应矩阵和基础矩阵 ComputeH21 结束 返回 FindHomographyFindHomography 跳转 CheckHomographyCheckHomography 结束 返回 F
  • Ubuntu 18.04 (Jetson Nano 4G/TX2)配置 CCM-SLAM

    文章目录 1 安装ROS2 安装OpenCV33 设置虚拟内存4 安装CCM SLAM 记录了安装CCM SLAM的详细过程以及踩过的坑 安装环境 xff1a Jetson Nano 4G Ubuntu 18 04 1 安装ROS 1 1更
  • Jetson Nano 调用CSI摄像头运行CCMSLAM

    文章目录 1 安装ROS的CSI摄像头软件包1 1 jetson csi cam1 2 jetson nano csi cam 2 修改Client0 euroc launch3 编写启动文件4 启动 1 安装ROS的CSI摄像头软件包 T
  • ROS多机通信SSH远程运行CCMSLAM

    文章目录 测试通信设置ROS MASTER URI主机rex终端输入 xff1a 从机nano终端输入 xff1a 启动CCMSLAM主机rex从机nano查看效果 SSH远程控制配置SSH启动SSH进行远程控制 背景 xff1a 主机 x
  • ORB2单目读代码笔记13--卡方检验原理及其在ORB-SLAM2中的用处

    卡方检验原理及其在ORB SLAM2中的用处 补 xff1a 卡方检验 补 xff1a 卡方检验 显著性水平 xff1a 显著性水平是估计总体参数落在某一区间内 xff0c 可能犯错误的概率 xff0c 用 表示 是指当原假设为正确时人们却
  • 玩转 Jetson Nano——开机准备与远程连接设置

    Nano开机准备与远程连接设置 1 开机前的准备1 1 认识 Nano1 2 硬件准备1 2 1 必备1 2 2 选配 1 3 在 SD 卡上烧写系统1 3 1 下载镜像1 3 2 格式化 SD 卡1 3 3 将镜像烧录到 SD 卡 1 4
  • CMAKE学习笔记

    文章目录 CMAKE常用指令CMake最低版本要求项目名称设置编译方式编译CXX的设置标志搜索外部库添加源文件子目录 查找源文件生成可执行文件生成链接库文件为可执行文件链接库指定头文件搜索路径SET定义变量LIST列表操作判断语句循环语句
  • 你所不知道的C语言——链表

    linus嘴里的good taste 在一次TED演讲中 xff0c 林老大在14分钟提到 xff0c 代码的品味 The mind behind linux 说实话 xff0c 这是我第一次听到林老大的声线 看下边一段代码 xff1a s