当前位置：首页 > 编程日记 > 正文

C语言的单链表求交点

编程日记 2024-04-23 13:00:00

单链表求交点，问题如下：
在这里插入图片描述
使用o(1)的空间复杂度，求两个链表相交的时候的交点，这个思想就类似于使用o(1)的空间复杂度和o(n)的时间复杂度来求链表的第k个节点。

过程如下：

获取两个链表的长度
将较长的链表移动和短链表长度差值的位置
移动后两个链表长度一样，然后一起移动，这样就知道节点相等的时候链表相交

算法实现如下:get_intersection_node函数

/*获取交叉链表的节点*/
Data *get_intersection_node(Data *headA, Data *headB) {int lenA;int lenB;lenA = get_len(headA);lenB = get_len(headB);/*平衡较长的链表，缩减长度*/if (lenA > lenB) {headA = equal_link(lenA,lenB,headA);} else {headB = equal_link(lenB,lenA,headB);}while(headA && headB) {/*本代码用于测试，根据链表的data域进行判断，正规是判断两链表指针域是否相等*/if(headA->data == headB->data) {return headA;}headA = headA -> next;headB = headB -> next;}return NULL;
}

源码实现如下：

#include <stdio.h>
#include <stdlib.h>typedef struct link_list {int data;struct link_list *next;
}Data;void print_list(Data *head) {while (head) {printf("%d ",head->data);head = head -> next;}printf("\n");
}Data *insert_tail(Data *head, int n) {head = (Data *)malloc(sizeof(Data));head -> next = NULL;Data *r = head;int data;while(n--) {Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &data);p -> data = data;r -> next = p;r = p;p -> next = NULL;}return head;
}/*获取链表的长度*/
int get_len(Data *head) {int len = 0;while (head -> next) {len ++;head = head -> next;}return len;
}/*将较长的链表长度缩减指定的差值*/
Data *equal_link(int longLen, int shortLen, Data *head) {int delta = longLen - shortLen;while (head && delta) {head = head -> next;delta --;}return head;
}/*获取交叉链表的节点*/
Data *get_intersection_node(Data *headA, Data *headB) {int lenA;int lenB;lenA = get_len(headA);lenB = get_len(headB);if (lenA > lenB) {headA = equal_link(lenA,lenB,headA);} else {headB = equal_link(lenB,lenA,headB);}while(headA && headB) {/*本代码用于测试，根据链表的data域进行判断，正规是判断两链表指针域是否相等*/if(headA->data == headB->data) {return headA;}headA = headA -> next;headB = headB -> next;}return NULL;
}
int main() {Data *headA;Data *headB;Data *result;printf("construct first link list :\n");headA = insert_tail(headA,5);printf("construct second link list :\n");headB = insert_tail(headB, 3);result = get_intersection_node(headA,headB);if (result){printf("intersection node is %d\n",result -> data);}else {printf("there is no intersection node\n");}return 0;
}

输出如下:

construct first link list :
1 2 3 4 5
construct second link list :
3 4 5
intersection node is 3

https://www.dkcj.cn/info/5108.html

jquery中如何以逗号分割字符串_百度知道

jquery中如何以逗号分割字符串_百度知道javascript本身就是带split方法的定义和用法split() 方法用于把一个字符串分割成字符串数组。语法stringObject.split(separator,howmany)参数描述separator 必需。字符串或正则表达式，从该参数指定的地方分割 stringObject。…

编程日记2024/04/23 12:30:00

mysql 前台启动_从Windows命令行启动MySQL

可以从命令行手动启动MySQL服务器。可以在任何版本的Windows中实现。要想从命令行启动mysqld服务器，你应当启动控制台窗口(或“DOS window”)并输入命令：C：\> C:\Program Files\MySQL\MySQL Server 5.0\bin\mysqld根据系统中MySQL安装位置…

编程日记2024/04/23 12:00:00

设置datagridview的数据源为（DATASET）SQL查寻结果

private void button5_Click(object sender, EventArgs e)02 {03 if (MessageBox.Show("确认删除该行吗？", "删除", MessageBoxButtons.YesNo, MessageBoxIcon.Question) DialogResult.Yes )04 {05 SqlConnection conn new SqlConnection();0…

编程日记2024/04/23 11:30:00

vim中文手册

http://vimcdoc.sourceforge.net/doc/help.html转载于:https://www.cnblogs.com/answercard/p/10125611.html

编程日记2024/04/23 11:00:00

C语言单链表求环，并返回环的起始节点

若链表中存在环，找出其中的环所在的节点，否则，返回NULL 在没有C set容器的优势前提下，我们对这样的环型的寻找以及定位可以利用快慢指针来实现。有环的存在，类似与操场跑圈，必然存在快慢之分。有了快慢&a…

编程日记2024/04/23 10:30:00

CSS3无前缀脚本prefixfree.js与Animatable使用介绍

要求必备知识本文要求基本了解 JAVASCRIPT 和和 CSS3 基本知识。运行环境桌面端:IE9 ，Opera 10，火狐3.5 ，Safari 4和Chrome浏览器;移动端:移动Safari，Android浏览器，Chrome浏览器和Opera Mobile。演示地址演示…

编程日记2024/04/23 10:00:00

mysql的优化之table_open_cache 篇_mysql性能优化之table_open_cache

表现：数据库查询效率慢，show processlist 发现比较多的查询正在opening table。进一步确认，执行以下语句：mysql> show global status like open%tables%;------------------------| Variable_name | Value |----------------…

编程日记2024/04/23 09:30:00

AIX系统日志学习笔记之一

AIX系统上线之后，难免会出现错误，为了应对错误，aix提供了很多处理错误的方法和日志记录机制，为修复故障和系统提供方便。 Errdemon是aix的一个守护进程，该进程会实时检查/dev/drror设备文件，查看是否有新的…

编程日记2024/04/23 09:00:00

C语言的单链表分割

已知链表头指针head与数值x，将所有小于x的节点放在大于或等于x 的节点前，且保持这些节点的原来的相对位置。这个过程有点类似于快速排序，寻找一个阈值，比该阈值小的放左边，比该阈值大的放右边。只是由数组遍历变为来…

编程日记2024/04/23 08:30:00

java面试时候算法题多吗_java程序员面试中最容易被问到的18个算法题（附答案！）...

作者：cpp软件架构狮链接：https://www.toutiao.com/i6618515311836529156/(点击阅读原文前去围观)算法是比较复杂又基础的学科，每个学编程的人都会学习大量的算法。而根据统计，以下这18个问题是面试中最容易遇到的，本文…

编程日记2024/04/23 08:00:00

Ubantu Mark

说明：由于图形化界面方法（如Add/Remove... 和Synaptic Package Manageer）比较简单，所以这里主要总结在终端通过命令行方式进行的软件包安装、卸载和删除的方法。一、Ubuntu中软件安装方法 1、APT方式 （1）普…

编程日记2024/04/23 07:30:00

Linux挂载Windows共享目录

手工挂载： mount -t cifs -o usernameXXX,passwordXXX //IP/共享目录 /挂载目录自动挂载： 在etc/fstab加入 //IP/共享目录 /挂载目录 cifs defaults,auto,usernameXXX,passwordXXX 0 0 重启转载于:https://blog.51cto.com/kenzhuang/1149033

编程日记2024/04/23 07:00:00

搭建私有npm私库（使用verdaccio）

一、为什么要搭建npm私库原因:1）公司内部开发的私有包，统一管理，方便开发和使用；2）安全性，由于公司内部开发的模块和一些内容并不希望其他无关人员能够看到，但是又希望内部能方便使用&#xff…

编程日记2024/04/23 06:30:00

C语言的有序单链表合并

已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为有序的，返回合并后的头节点。主要步骤如下： 创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点当headA->data 比headB-&g…

编程日记2024/04/23 06:00:00

我的世界java版双海底神殿种子_我的世界海底神殿种子2021

游戏我的世界中，2021年的海底神殿地图中有五种类型的种子可以使用，建议在找海底神殿时使用夜视药水。那么2021年在MC中最新的海底神殿种子分别是Seed：-1005362104，Seed：-1436927780，Seed：-10053…

编程日记2024/04/23 05:30:00

Erlang服务端开发（无需Erlang基础）笔试题

某游戏公司Erlang服务端开发（无需Erlang基础）笔试题，面向C/C程序员一、用你熟悉的语言解决下面的问题。 1、反转输出字符串，并移除其中的空格。 2、快速的判断一个数是否素数的方法。 3、给一个数组进行排序。 4、设计一个背包系…

编程日记2024/04/23 05:00:00

几何匹配和分合算法的图像识别技术

第一章引言 1.1 面像定位概述及其与面像识别的关系这个设计所涉及到的是面像的定位和识别。简单来说，所谓面像的定位，就是在照片(静态图像)或视频(动态图像)中标出面像所在的位置，把面像选取出来。而面像的识别就是把选取出来的面像与…

编程日记2024/04/23 04:30:00

RegExp 正则

正则：就是一条规则，用于检验字符串的格式，目标就是字符串。只要是表单提交的数据都是字符串正则的定义： 1.var regnew RegExp()； 2.var reg/格式/； 正则的方法： 两个功能，一个是匹…

编程日记2024/04/23 04:00:00

C++的多个有序链表合并

已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的 ，返回合并后的头节点如下三个链表： 合并后的结果如下： 方法一（STL sort算法进行排序）： 先将输入的排序链表插入…

编程日记2024/04/23 03:30:00

c# 垃圾回收是引用类型而言的

c# 垃圾回收是引用类型而言的转载于:https://www.cnblogs.com/C-CHERS/p/3646387.html

编程日记2024/04/23 03:00:00

java unlimited_具有无限参数的Java方法(Java method with unlimited arguments)

具有无限参数的Java方法(Java method with unlimited arguments)Spring框架使用方法，您可以根据需要传递尽可能多的参数。我想写一个函数，也可以采取无限量的数据。这个功能是如何调用的，以便我可以阅读它。或者我该如何定义它？…

编程日记2024/04/23 02:30:00

2013-3-10日记

2019独角兽企业重金招聘Python工程师标准>>> 今天星期日，在家早上看NBA，中午去买菜，下午在家种花，晚上看CBA。转载于:https://my.oschina.net/guanyun/blog/112801

编程日记2024/04/23 02:00:00

P1522 牛的旅行

这题挺好……有几个坑……（反正我都跳进去了） 对于新的更大的图，由于求的是最小连接边，所以它的值可能小于之前单独一个图的最长的最短路…… 所以之后的值应该取个max（emmm……） 所以第一次我只拿了70。。…

编程日记2024/04/23 01:30:00

C++ algorithm的sort函数总结

sort函数 sort对给定区间进行排序，支持各种数据类型，迭代器，结构体，自定义排序规则stable_sort 对给定区间进行稳定排序,且可保证相等元素的原本相对次序在排序后保持不变partial_sort 对给定区间部分元素排序partial_sort_copy …

编程日记2024/04/23 01:00:00

加密解密php,PHP实现的加密解密处理类

本文实例讲述了PHP实现的加密解密处理类。分享给大家供大家参考，具体如下：/* 版权协议： GPL (The GNU GENERAL PUBLIC LICENSE Version 2, June 1991)------------------------------------------------------------ 文件名称：cls…

编程日记2024/04/23 00:30:00

技术人生：本周改进计划

分配时间学习领域知识和管理知识。更慎重的命名。注意交流的态度和方式（特别是在出现不同意见的时候）。对待任何工作内容都不能应付了事。转载于:https://www.cnblogs.com/happyframework/p/3695596.html

编程日记2024/04/23 00:00:00

linux下batik-rasterizer.jar生成图片中文乱码

为什么80%的码农都做不了架构师？>>> 发现原来jdk5.0在linux下和以前的版本还不一样，默认不支持中文字体的。得手动去搞一个fontconfig配置， 此文件在$JAVA_HOME/jre/lib/下， 果然有一大堆fontconfig.XX.properties, 官…

编程日记2024/04/22 23:30:00

小记，springboot项目中自己常用的logback配置文件

把配置文件放到resources这个classpath目录即可生效，日志输入样式是从springboot中日志配置中copy过来的, 其他常用配置不做过多注释了。 logback-spring.xml <?xml version"1.0" encoding"UTF-8"?> <configuration><conversi…

编程日记2024/04/22 23:00:00

s-sar命令（System Activity Reporter系统活动情况报告）

文章目录前言语法格式查看CPU使用情况保存统计结果到文件中查看磁盘平均负载和队列长度查看内存使用情况查看系统swap分区情况查看IO和传递速率查看磁盘使用情况输出inode、文件和其他内核表的信息统计网络信息查看网络接口信息网络设备通信失败信息统计socket连接信息TCP连接的…

编程日记2024/04/22 22:30:00

基础设计模式：单例模式+工厂模式+注册树模式

单例模式： 通过提供自身共享实例的访问，单例设计模式用于限制特定对象只能被创建一次。使用场景： 一般数据库实例都会用单例模式实现： 单例设计模式就是要一个类只能实例化一个对象。要想让一个类只能实例化一个对象&#xff0…

编程日记2024/04/22 22:00:00

相关文章：