目录
前言
1.题目一:链表分割
1.1 思路
1.2 分析
1.3 题解
2. 题目二:相交链表
2.1 思路
2.2 分析
2.3 题解
3. 题目三:环形链表
3.1 思路
3.2 分析
3.3 题解
总结
前言
本期继续分享链表相关的OJ题目,在这个专栏博客中,我们将提供丰富的题目资源和解题思路,帮助读者逐步提高解题能力。同时,我们也将分享一些刷题技巧和经验,帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践,相信读者可以在数据结构领域取得长足的进步。
1.题目一:链表分割
题目描述:
题目链接:
链表分割https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
1.1 思路
这道题目没有示例,这也是这道题的难点之一,我们只根据题意自己寻找示例,进行分析。题目的意思是说,给一个链表,给一个x值,把小于x的插入到x前边,大于x的插入到x的后边,且不可以打乱原链表中的次序(链表中的数据大小为乱序)。理解了题意,大家可以先自己思考一下解题思路。
对于这道题的要求我们可以这样做:遍历原链表,将大于等于x的尾插到一个新链表,小于x的尾插到一个新链表,最后将两个链表合并。
1.2 分析
这道题思路虽然非常简单,但是在实际编写代码时会有很多的坑。例如要考虑链表为NULL的情况,如果原链表中的所有值都大于x或小于x那就会造成两个链表中,其中一个链表为NULL。
假设原链表为:
x值为3,那我们就可以把原链表分割成以下两个链表:
这道题目有两种方法,一种是使用带头节点的链表,一种是使用不带头节点的链表。对于链表掌握不熟悉的,本人推荐使用带头节点的链表,当然带头节点的链表对于这道题也可以简化代码。如果没有带头节点,那我们在初始化后尾插时就需要进行特殊处理。相对比较麻烦,所有我们这里推荐使用带头链表。
如果带头结点两链表就是这样的:
将两个链表合并时也不需要特殊处理可以直接连接,如下图:
不用担心头节点怎么办,两个头节点最后会被销毁,销毁之后就是我们所需要的链表了。
就算是第一个链表为空,也可以搞定:
连接的时候也不需要特殊处理,最后销毁两个头节点即可。
1.3 题解
根据分析的思路,我们对代码进行编写:
ListNode* partition(ListNode* pHead, int x) {struct ListNode* head1,*head2,*tail1,*tail2;head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));//创建两个头节点head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=pHead; while(cur) //遍历原链表{if(cur->val < x) //小于x就尾插到链表1{tail1->next=cur;tail1=tail1->next;}else //大于等于x就尾插到链表2{tail2->next=cur;tail2=tail2->next;}cur=cur->next; }tail1->next=head2->next; //将两个链表合并tail2->next=NULL;struct ListNode* head=head1->next;free(head1);free(head2);return head; //最后返回链表1的第一个节点}
2. 题目二:相交链表
题目描述:
示例:
题目链接:
相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
2.1 思路
这道题目的解题思路就简单了,但要注意链表长度不同的情况。当两个节点的节点个数不相同时,指向长链表的指针要先走它们节点个数的差值步。然后开始一一对比,直到遇到相交节点为止。
2.2 分析
链表相交并不是像直线那样交叉相交,单链表中,一个节点只能指向一个节点,所有这里的链表相交是如下图的情况:
总体分 3 步:
- 先遍历两个链表得到两个链表的长度。
- 长的链表先走差距步(len1-len2)。
- 开始遍历两个数组,直到相交点,返回相交的节点
2.3 题解
整理完思路后,根据分析的思路进行编写代码:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB) //如果遍历到最后两个链表的尾节点不是同一个节点就说明不相交。{return NULL;}int t= abs(lenA-lenB);//求出差距步 abs是求绝对值的函数struct ListNode* longlist=headA, *shortlist=headB;if(lenB>lenA) //这里先假设链表A长,如果不是链表A长就交换一下,简化代码{longlist=headB;shortlist=headA;}while(t--) //长的链表走差距步{longlist=longlist->next;}while(longlist!=shortlist)//两链表同时遍历{longlist=longlist->next;shortlist=shortlist->next;}return longlist; //循环停止时指向的节点就是第一个相交节点,返回它们两个任意一个
}
3. 题目三:环形链表
题目描述:
示例:
题目链接:
环形链表https://leetcode.cn/problems/linked-list-cycle/description/
3.1 思路
我们知道循环链表,循环链表的尾指向链表的头,遍历一遍之后会回到链表的头,但这道题属于带环链表,带环链表的尾不一定连接着头,它可能连接着任意节点。带环链表的题目属于链表中较为复杂的题目,那要如何判断一个链表是否带环呢?
首先我们知道,带环链表在向后遍历的时候,一定会回到入环点,比较链表中的节点是否为入环时的节点就可以了,但是问题来了,我们怎么知道哪个是开始入环的节点?不知道入环的节点又怎么比较是否是同一个节点。显然传统的思路行不通,那我们就来换一种方法。
这里我们就可以使用快慢指针的方法,一个指针走的快一个指针走的慢,当快的指针再次与慢指针相遇,那就说明这个链表一定是带环链表。
3.2 分析
带环链表的入环节点可能是任意节点:
它也可以指向它自己。
这里我们可以使用快慢指针的方法,使用快指针来追击慢指针,当快指针与慢指针再次相遇,这就说明这个链表一定为带环链表,但是如果快指针走到了NULL,这就说明这个链表不是带环链表。
3.3 题解
根据分析的思路,我们整理一下,形成代码:
bool hasCycle(struct ListNode *head) {struct ListNode* fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;
}
题解也是非常简单。对于带环链表,今天这道题目属于热身,下期我会专门出一期带环链表的题目。
总结
最后,感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力,不断探索和挑战,成为数据结构领域的行家里手!