单链表算法题(数据结构)

devtools/2024/11/14 10:29:13/

1. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

题目

看到这个题目的时候我们怎么去想呢?如果我们反应快的话,应该可以想到我们可以从1遍历到5然后依次头插,但是其实我们还有更好的办法,就是利用三个指针,如何使用呢?

反转链表OJ
假如结构体已经给出
typedef struct ListNode SL;
SL* reverseList(SL* head)
{//处理空链表if (head == NULL){return head;}else{//创建三个指针SL* n1, n2, n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;}
}

 2. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/
题目
 这个题目就是在一个链表中我们要返回中间结点,如果中间结点有两个的话就返回第二个结点。

对于这个题目我们可能会想到一个简单的思路,就是遍历两边数组然后找到中间的一个结点,但是呢,今天讲一个更方便的算法叫做快慢指针,也就如上图所示,一个慢指针和一个快指针,快指针走两步慢指针走一步,最终当快指针走到终的时候慢指针刚好就在中间,让我们来实现一下:

//找链表的中间结点
//Definition for singly-linked list.
struct ListNode
{int val;struct ListNode *next;
};typedef struct ListNode SL;
struct ListNode* middleNode(struct ListNode* head)
{SL* slow = head;SL* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

再上一个题目中我们有一个点需要注意就是我们在写while循环的条件时候注意不能将fast&&fast->next的位置搞反,原因就是不能解引用空指针,所以顺序一定注意一下。

3.  合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。这个题目的思路也很好想出来,我们可以遍历两个升序链表,然后创建一个新的链表,将遍历的结点按升序放入新的链表中,要注意链表为空的情况。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode SL;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//创建新的链表SL* newhead=NULL;SL* newtail=NULL;//创建两个指针分别指向两个链表SL* l1=list1;SL* l2=list2;//判断两个链表是否为空if(list1==NULL){return l2;}if(list2==NULL){return l1;}while(l1&&l2){if(l1->val<=l2->val){//l1尾插到新链表中if(newhead==NULL){newhead=newtail=l1;}else{newtail->next=l1;newtail=newtail->next;}l1=l1->next;}else{//l2尾插到新链表中if(newhead==NULL){newhead=newtail=l2;}else{newtail->next=l2;newtail=newtail->next;}l2=l2->next;}}//跳出循环有两种情况,要么l1为空,要么l2为空if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead;
}

4. 链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

什么是回文结构?比如1221,它看起来像是对称的可以从中间重叠的感觉,叫做回文数字。像上图1->2->2->1,就是链表的回文结构。我们就是思考如何去判读一个链表是否是回文结构。我们可能会想到说这个题目需要去遍历比较是否相等,但是有一个问题就是在单链表中是不能向后遍历的,又因为这个题目是的链表长度是有限的,所以我们不妨把链表放入数组中来比较,那么如何操作呢?

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here//创建一个数组int arr[900] = {0};ListNode* pcur = A;int i = 0;//遍历链表,将链表中的每个结点的数值放入数组中while(pcur){arr[i++] = pcur->val;pcur=pcur->next;}//找中间结点,判断是否是回文数字int left=0;int right=i-1;while(left<right){if(arr[left]!=arr[right]){return false;}left++;right--;}return true;}
};

对于这个题目来说,它是有限制的,所以我们可以放在数组中去双向遍历,但是一旦链表没有限制,我们就不能这样来写,我们可以有另一种方法,我们的前两道题目是反转链表和找中间结点,看下面的图,如果是回文链表的话我们可以先找到中间结点,然后将其反转成为一个新的链表,再创建两个指针遍历链表,判断链表结点是否相等,最终以一个指针为NULL而结束。

5. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//创建两个指针遍历链表ListNode* l1=headA;ListNode* l2=headB;//先计算两个链表的长度int sizeA=0;int sizeB=0;while(l1){sizeA++;l1=l1->next;}while(l2){sizeB++;l2=l2->next;}//得出了两个链表的长度//计算两数之差int gap=abs(sizeA-sizeB);//让长链表先走gap步ListNode* longlist=headA;ListNode* shortlist=headB;if(sizeA<sizeB){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}//此时在同一个起点处,进行两个链表结点的比较while(longlist&&shortlist){if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}//链表不相等return NULL;
}

 6. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

题目:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 。 否则,返回 false 。

💡 快慢指针
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,
如果链表带环则一定会在环中相遇,否则快指针率先走到链表的未尾。

对于这个题目我们可以使用快慢指针的方法进行解题,因为在环形链表中一个慢指针每次走一步一个快指针每次走两步一定还会相遇,如果相遇的话那么就证明这个链表是环形链表,为什么快慢指针一定会相遇呢?当slow和fast进入环之后,此时快慢指针在环里开始进行追逐,大家会发现它们之间的距离越来越凶小,从N变成N-1变成N-2....一直到0就是指针相遇。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode SL;
bool hasCycle(struct ListNode *head) 
{SL* slow=head;SL* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}//两个指针始终没有相遇return false;
}
思考2:快指针一次走3步,走4步,...n步行吗?
按照上面的分析,慢指针每次走一步,快指针每次走三步,此时快慢指针的最大距离为N,接下来的追逐过程中,每追击一次,他们之间的距离缩小2步,追击过程中fast和slow之间的距离变化:

 

分析:
1、如果N是偶数,第⼀轮就追上了
2、如果 N是奇数 ,第⼀轮追不上,快追上,错过了,距离变成-1,即C-1,进⼊新的⼀轮追击
a、C-1如果是偶数,那么下⼀轮就追上了
b、 C-1如果是奇数, 那么就永远都追不上
总结⼀下追不上的前提条件: N是奇数,C是偶数

 

假设:
环的周长为C,头结点到slow结点的长度为L,slow走⼀步,fast走三步,当slow指针入环后,
slow和fast指针在环中开始进行追逐,假设此时fast指针已经绕环x周。
在追逐过程中,快慢指针相遇时所走的路径长度:
fast: L+xC+C-N
slow L
由于慢指针走一步,快指针要走三步,因此得出: 3 * 慢指针路程 = 快指针路程 ,即:
3 L = L + xC + C N
2 L = ( x + 1) C N
对上述公式继续分析:由于偶数乘以任何数都为偶数,因此 2L一定为偶数,则可推导出可能得情
况:
情况1:偶数 = 偶数 - 偶数
情况2:偶数 = 奇数 - 奇数
由step1中(1)得出的结论,如果N是偶数,则第⼀圈快慢指针就相遇了。
由step1中(2)得出的结论,如果N是奇数,则fast指针和slow指针在第⼀轮的时候套圈了,开始进行下⼀轮的追逐;当N是奇数,要满足以上的公式,则 (x+1)C 必须也要为奇数,即C为奇数,满足a中的结论,则快慢指针会相遇。
因此, step1 中的 N 是奇数, C 是偶数 ,既然不存在该情况,则快指针⼀次⾛3步最终⼀定也
可以相遇。

 

 

 

 

 

 


http://www.ppmy.cn/devtools/133318.html

相关文章

pytorch量化训练

训练时量化&#xff08;Quantization-aware Training, QAT&#xff09;是一种在模型训练过程中&#xff0c;通过模拟低精度量化效应来增强模型对量化操作的鲁棒性的技术。与后训练量化不同&#xff0c;QAT 允许模型在训练过程中考虑到量化引入的误差&#xff0c;从而在实际部署…

【NLP】使用 SpaCy、ollama 创建用于命名实体识别的合成数据集

命名实体识别 (NER) 是自然语言处理 (NLP) 中的一项重要任务&#xff0c;用于自动识别和分类文本中的实体&#xff0c;例如人物、位置、组织等。尽管它很重要&#xff0c;但手动注释大型数据集以进行 NER 既耗时又费钱。受本文 ( https://huggingface.co/blog/synthetic-data-s…

【C语言】分布式系统

描述一下你对分布式系统的理解&#xff0c;以及如何设计和实现一个分布式系统。 分布式系统是由多台独立计算机通过网络协同工作的集合&#xff0c;它们各自运行着完整的应用程序和数据库&#xff0c;并相互之间通过通信协议进行数据交换和协调任务。分布式系统的主要特性包括&…

(十三)JavaWeb后端开发——MySQL2

目录 1.DQL数据查询语言 1.1基本查询 1.2条件查询 where关键字 1.3分组查询 1.4排序查询 1.5分页查询 2.多表设计 3.多表查询——联查 4.多表查询——子查询​ 5.MySQL 事务 6.事务管理&#xff08;事务进阶&#xff09; 7.MySQL 索引 1.DQL数据查询语言 分为五大…

SpringBoot框架:共享汽车行业的技术革新

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了共享汽车管理系统的开发全过程。通过分析共享汽车管理系统管理的不足&#xff0c;创建了一个计算机管理共享汽车管理系统的方案。文章介绍了共享汽车管理系统的系…

《Atomic Picnic》进不去游戏解决方法

Atomic Picnic有时候会遇到进不去游戏的情况&#xff0c;这可能是由多种原因造成的&#xff0c;玩家可以采取很多解决方法&#xff0c;比如检查电脑配置、更新系统和驱动或验证游戏文件。 Atomic Picnic进不去游戏怎么办 检查电脑配置 查看自己的电脑配置是否达到了游戏的要求…

PySimpleGUI 库 和 pymsql 库

PySimpleGUI 库 PySimpleGUI 是一个用于简化 GUI 编程的 Python 包&#xff0c;它封装了多种底层 GUI 框架&#xff08;如 tkinter、Qt、WxPython 等&#xff09;&#xff0c;提供了简单易用的 API。PySimpleGUI 包含了大量的控件&#xff08;也称为小部件或组件&#xff09;&…

阿里云centos7.9服务器磁盘挂载,切换服务路径

项目背景 1、项目使用的服务器为阿里云centos7.9&#xff0c;默认的磁盘为vda&#xff0c;文件系统挂载在这个磁盘上&#xff0c;项目上使用的文件夹为/home/hnst/uploadPath 2、vda使用率已达到91% 3、现购置一块新的磁盘为vdb&#xff0c;大小为2T 目的 切换服务所使用的…