[数据结构]链表OJ

news/2024/3/19 10:24:10/文章来源:https://blog.csdn.net/qq_66767938/article/details/129179650

目录

数据结构之链表OJ::

                                     1.移除链表元素

                                     2.反转链表

                                     3.链表的中间结点

                                     4.链表中倒数第k个结点

                                     5.合并两个有序链表

                                     6.链表分割

                                     7.链表的回文结构

                                     8.相交链表

                                     9.环形链表

                                    10.环形链表II

                                    11.复制带随机指针的链表


数据结构之链表OJ::

1.移除链表元素

删除链表中等于给定值val的所有结点
struct ListNode
{int val;struct ListNode* next;
};
方法一
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, * prev = NULL;while (cur != NULL){//1.头删//2.非头删if (cur->val == val){if (cur == head){head = head->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}
不用二级指针的方法:返回头指针
main函数调用方式:plist = removeElements(plist,6);
方法二
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* newhead = NULL, * tail = NULL;while (cur != NULL){if (cur->val != val){if (tail == NULL){newhead = tail = cur;}else{tail->next = cur;tail = tail->next;}}else{struct ListNode* del = cur;cur = cur->next;free(del);}}if (tail != NULL){tail->next = NULL;}return newhead;
}
方法三:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail = guard;while (cur != NULL){if (cur->val != val){tail->next = cur;tail = tail->next;cur = cur->next;}else{struct ListNode* del = cur;cur = cur->next;free(del);}}最后结点是val 就会出现此问题if (tail != NULL){tail->next = NULL;}head = guard->next;free(guard);return head;
}
替代我们之前实现的二级指针
1.返回新的链表头 2.设计为带哨兵位

2.反转链表

反转链表
方法一:取结点头插到新链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;
}
方法二:翻转链表方向
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1, *n2, *n3;n1 = NULL;n2 = head;n3 = NULL;while (n2){n3 = n2->next;n2->next = n1;迭代n1 = n2;n2 = n3;}return n1;
}

3.链表的中间结点

链表的中间结点——快慢指针
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

4.链表中倒数第k个结点

链表中倒数第k个结点——快慢指针
方法一:
struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
{struct ListNode* fast, * slow;fast = slow = pListHead;while (k--) 走k步{k大于链表长度if (fast == NULL)return NULL;fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow;
}
方法二:
struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
{struct ListNode* fast, * slow;fast = slow = pListHead;while (fast && --k)走k-1步{k大于链表长度	fast = fast->next;}if (fast == NULL)return NULL;while (fast->next){slow = slow->next;fast = fast->next;}return slow;
}

5.合并两个有序链表 

合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));guard->next = NULL;struct ListNode* tail = guard;struct ListNode* cur1 = list1, * cur2 = list2;while (cur1 && cur2){if (cur1->val < cur2->val){tail->next = cur1;cur1 = cur1->next;}else{tail->next = cur2;cur2 = cur2->next;}tail = tail->next;}if (cur1)tail->next = cur1;if (cur2)tail->next = cur2;struct ListNode* head = guard->next;free(guard);return head;
}

6.链表分割 

链表分割
struct ListNode* partition(struct ListNode* pHead, int x)
{struct ListNode* lessGuard, * lessTail, * greaterGuard, * greaterTail;lessGuard = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterGuard = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessGuard->next = NULL;greaterGuard->next = NULL;struct ListNode* cur = pHead;while (cur){if (cur->val < x){lessTail->next = cur;lessTail = lessTail->next;}else{greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}lessTail->next = greaterGuard->next;greaterTail->next = NULL;pHead = lessGuard->next;free(greaterGuard);free(lessGuard);return pHead;
}

7.链表的回文结构 

链表的回文结构
方法一:找中间结点翻转链表
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = NULL;while (n2){n3 = n2->next;n2->next = n1;n1 = n2;n2 = n3;}return n1;
}
bool chkPalindrome(struct ListNode* head)
{struct ListNode* mid = middleNode(head);struct ListNode* rmid = reverseList(mid);while (head && rmid){if (head->val != rmid->val)return false;head = head->next;rmid = rmid->next;}return true;
}
方法二:整个链表逆置看和链表是否相同 但要注意需要重新拷贝原链表

8.相交链表 

相交链表
判断是否相交判断尾结点的地址是否相同
找交点:求出长度lenA lenB 长的链表先走差距步 第一个相等的就是交点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{if (headA == NULL || headB == NULL){return NULL;}struct ListNode* curA = headA, * curB = headB;int lenA = 1;找尾结点while (curA->next){curA = curA->next;++lenA;}int lenB = 1;while (curB->next){curB = curB->next;++lenB;}if (curA != curB){return NULL;}struct ListNode* longList = headA, * shortList = headB;if (lenA < lenB){longList = headB;shortList = headA;}长的链表先走差距步int gap = abs(lenA - lenB);while (gap--){longList = longList->next;}同时走找交点while (longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

9.环形链表 

环形链表
快慢指针法:slow进环以后 fast开始追赶slow 
bool hasCycle(struct ListNode* head)
{struct ListNode* fast, * slow;fast = slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)return true;}return false;
}
请证明一下,slow走一步 fast一次走两步?
请证明一下,slow走一步 fast一次走三步?是否可以? 答:不一定
请证明一下,slow走一步 fast一次走X步?是否可以?每次缩小X-1
请证明一下,slow走X步  fast一次走Y步?是否可以?X<Y 每次缩小X-Y
fast走两步时:假设slow进环以后 fast slow之间的差距为N 即追赶距离为N
slow和fast每移动一步 距离缩小1 距离缩小为N N-1 N-2...1 0 距离为0即相遇
fast走三步时:假设slow进环以后 fast slow之间的差距为N 即追赶距离为N
slow每追赶一次 它们之间距离缩小两步 距离变化为N N-2 N-4 N-6...
如果N为偶数则能追上 如果为奇数距离由1变为-1 意味着它们之间的距离变为了C-1(C是环的长度)
如果环减一是偶数再追一圈就能追上 如果环减一为奇数 则永远追不上

10.环形链表II

环形链表II
1.公式证明推导
2.转换成相交问题
fast走的距离 = 2*slow走的距离
假设进环前的长度是L
假设环的长度是C
假设入口点到相遇点距离是X
slow走的距离是L+X
fast走的距离是L+C=X
假设slow进环前 fast在环里面转了N圈 N>=1
2(L+X) = L+X+N*C
(L+X) = N*C
L = N*C-X
L = (N-1)*C+C-X
结论:一个指针A从头开始走 一个指针B从相遇点开始走 它们会在入口点相遇
1.公式证明推导
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){struct ListNode* meet = slow;while (meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}
2.转换成相交问题
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{if (headA == NULL || headB == NULL){return NULL;}struct ListNode* curA = headA, * curB = headB;int lenA = 1;找尾结点while (curA->next){curA = curA->next;++lenA;}int lenB = 1;while (curB->next){curB = curB->next;++lenB;}if (curA != curB){return NULL;}struct ListNode* longList = headA, * shortList = headB;if (lenA < lenB){longList = headB;shortList = headA;}长的链表先走差距步int gap = abs(lenA - lenB);while (gap--){longList = longList->next;}同时走找交点while (longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){转换成相交struct ListNode* meet = slow;struct ListNode* next = meet->next;meet->next = NULL;struct ListNode* entryNode = getIntersectionNode(head, next);恢复环meet->next = next;return entryNode;}}return NULL;
}

11.复制带随机指针的链表

 

复制带随机指针的链表
方法一:1.遍历原链表 复制结点 尾插2.更新random 找random原链表中第i个 新链表中对应第i个
方法二:1.拷贝原结点 链接到所有原结点的后面ps:原结点和拷贝结点建立一个链接关系 找到原结点就可以找到拷贝结点2.更新每个拷贝结点的random 3.将拷贝结点解下来 链接成新链表
struct Node
{int val;struct Node* next;struct Node* random;
};
struct Node* copyRandomList(struct Node* head)
{1.插入copy结点struct Node* cur = head;struct Node* copy = NULL;struct Node* next = NULL;while (cur){next = cur->next;copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;cur->next = copy;copy->next = next;cur = next;}2.更新copy->randomcur = head;while (cur){copy = cur->next;if (cur->random == NULL)copy->random = NULL;elsecopy->random = cur->random->next;cur = cur->next->next;}3.copy结点要解下来链接在一起 恢复原链表struct Node* copyHead = NULL, * copyTail = NULL;cur = head;while (cur){copy = cur->next;next = copy->next;取结点尾插if (copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}恢复原链表链接cur->next = next;cur = next;}return copyHead;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_262334.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ARM uboot 源码分析6 - uboot如何启动内核

一、uboot 和内核到底是什么 1、uboot 是一个裸机程序 (1) uboot 的本质就是一个复杂点的裸机程序。和我们在 ARM 裸机全集中学习的每一个裸机程序并没有本质区别。 (2) ARM 裸机第十六部分写了个简单的 shell&#xff0c;这东西其实就是个mini 型的 uboot。 2、内核本身也是…

Hadoop Shell常用命令

Hadoop Shell命令在管理HDFS的时候还是比较常用的&#xff0c;Hadoop Shell命令与shell命令极为相似&#xff0c;但是方便查询&#xff0c;在这里总结分享&#xff0c;大家enjoy~~ 1&#xff0c;cat 语法格式&#xff1a;hadoop fs -cat URI [URI …] 含义&#xff1a;将路径…

【架构师】零基础到精通——架构演进

博客昵称&#xff1a;架构师Cool 最喜欢的座右铭&#xff1a;一以贯之的努力&#xff0c;不得懈怠的人生。 作者简介&#xff1a;一名Coder&#xff0c;软件设计师/鸿蒙高级工程师认证&#xff0c;在备战高级架构师/系统分析师&#xff0c;欢迎关注小弟&#xff01; 博主小留言…

华为OD机试题,用 Java 解【查找接口成功率最优时间段】问题

最近更新的博客 华为OD机试 - 猴子爬山 | 机试题算法思路 【2023】华为OD机试 - 分糖果(Java) | 机试题算法思路 【2023】华为OD机试 - 非严格递增连续数字序列 | 机试题算法思路 【2023】华为OD机试 - 消消乐游戏(Java) | 机试题算法思路 【2023】华为OD机试 - 组成最大数…

【数据库】redis集群环境详解

目录 集群环境 一&#xff0c;集群介绍 1、为什么需要redis集群 2、什么是redis集群 二&#xff0c;数据分片 三&#xff0c; 主从复制模型 四&#xff0c;一致性保证 五&#xff0c;集群搭建 1&#xff0c; 集群结构 2&#xff0c;创建配置文件 &#xff08;1&#…

RebbitMQ 消息队列(简单使用)

消息队列介绍 MQ的优势 1.业务解耦&#xff1a;不同系统消费信息互不关联&#xff0c;灵活增减系统数量&#xff0c;修改某个系统其他系统也不影响 2.异步提速&#xff1a;不同系统之间可同时响应&#xff0c;提升并发量 3.削峰填谷&#xff1a;处理消息高峰期&#xff0c;均摊…

Ubuntu通过kubeadm安装k8s

kubeadm kubeadm是一个构建k8s集群的工具。它提供的kubeadm init和 kubeadm join 两个命令是快速构建k8s集群的最佳实践。 其次&#xff0c;kubeadm工具只为构建最小可用集群&#xff0c;它只关心集群中最基础的组件&#xff0c;至于其他的插件&#xff08;比如dashboard、CNI…

SpringCloud - Gateway网关路由

目录 网关初步介绍 搭建网关服务 路由断言工厂Route Predicate Factory 路由过滤器 GatewayFilter 全局过滤器 GlobalFilter 过滤器执行顺序 网关的cors跨域配置 网关初步介绍 不是所有的请求&#xff0c;都能访问服务&#xff0c;所以需要网关对来访问的请求进行提前判…

java 9 的新特性解读(1)

前言  经过4次跳票&#xff0c;历经曲折的Java 9 终于终于在2017年9月21日发布。  从Java 9 这个版本开始&#xff0c;Java 的计划发布周期是 6 个月&#xff0c;下一个 Java 的主版本将于 2018 年 3 月发布&#xff0c;命名为 Java 18.3&#xff0c;紧接着再过六个月将发布…

CSS 盒子模型【快速掌握知识点】

目录 一、什么是盒子模型 二、边框border-color 三、边框粗细border-width 四、边框样式border-style 五、外边距margin 六、内边距padding 七、圆角边框 八、圆形 九、盒子阴影 一、什么是盒子模型 css盒子模型又称为框模型&#xff0c;盒子的最内部是元素的实际内容…

【Git】与“三年经验”就差个分支操作的距离

前言 Java之父于胜军说过&#xff0c;曾经一位“三年开发经验”的程序员粉丝朋友&#xff0c;刚入职因为不会解决分支问题而被开除&#xff0c;这是不是在警示我们什么呢&#xff1f; 针对一些Git的不常用操作&#xff0c;我们通过例子来演示一遍 1.版本回退 1.1已提交但未p…

notepad++如何快速批量搜索复制,3步搜索+标记所在行+复制书签行

一。缘起 用习惯了 某edit, 突然用notepad很不习惯&#xff0c;至少3处不习惯&#xff1a;列操作&#xff0c;批量复制搜索行&#xff0c;和是txt文件比较。 另外一直坚持认为&#xff0c;不提供快捷键操作的软件不是好软件&#xff1a;&#xff09;当下屏幕对眼睛迫害至深的时…

SGI 空间配置器

前言 空间配置器是 STL 六大组件之一&#xff0c;它总是隐藏在容器的背后&#xff0c;默默工作&#xff0c;默默付出。本文为《STL 源码剖析》读书笔记&#xff0c;主要讨论 SGI 版本空间的配置和释放&#xff0c;对代码进行解读时会改变一些写法&#xff0c;使其更易于阅读。…

企业急需:拥有一个属于自身的知识库!

如今&#xff0c;拥有知识库对任何企业来说都是绝对必要的。特别是在软件即服务方面。如果您真的希望您的 SaaS 业务取得成功&#xff0c;您需要从第一天开始构建知识库。为什么&#xff1f;首先&#xff0c;SaaS 公司有一个货币化模型&#xff0c;专注于他们的每月经常性收入 …

多传感器分布式融合算法——多传感器网络协同目标跟踪和定位

多传感器分布式融合算法 应用&#xff1a; 多传感器网络协同目标跟踪及定位 原创不易&#xff0c;路过的各位大佬请点个赞 主要讲解算法&#xff1a; 多传感器集中式融合算法/分布式融合算法/序贯融合算法 多速率多传感器异步融合算法 多传感器…

PHP程序员适合创业吗?

创业是一件自然而然的事&#xff0c;不需要人为选择。 只要你是一个努力能干主动的人&#xff0c;当你在一个行业深耕5年之后&#xff0c;就会发现人生发展的下一步就是创业。当然如果行业合适的话。 什么叫行业合适呢&#xff1f; 就是创业的成本并不那么高&#xff0c;不需…

js 实现 Logo(图片)根据图片后面的图片颜色而变化成相反的颜色【解决logo固定后 会出现与不同板块的颜色相同导致于看不清logo的情况】

效果展示&#xff1a; <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <meta http-equiv"X-UA-Compatible" content"ieedge"><style type"text/css…

Unreal Engine 虚幻引擎,性能分析,优化(二)

一、CPU 性能分析 如渲染线程中出现 CPU 受限&#xff0c;原因可能是绘制调用过多。这是一个常见问题&#xff0c;美术师通常会将绘制调用进行组合&#xff0c;从而减少消耗&#xff08;如&#xff1a;将多个墙壁组合为一个网格体&#xff09;。实际消耗存在于多个区域中&…

vue3路由守卫

文章目录路由守卫1.全局路由守卫2.组件内守卫3.路由独享守卫提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考路由守卫 全局守卫&#xff08;3个&#xff09; 路由独享守卫&#xff08;1个&#xff09; 组件的守卫&#xff08;3个&#xff09; 路由守卫的…

蓝牙运动耳机哪个好,比较好的运动蓝牙耳机

很多想选择蓝牙运动耳机的朋友都不知道应该如何选择&#xff0c;运动首先需要注意的就是耳机的防水能力以及耳机佩戴舒适度&#xff0c;在运动当中会排出大量的汗水&#xff0c;耳机防水等级做到越高&#xff0c;可以更好地保护耳机不受汗水浸湿&#xff0c;下面就分享五款适合…