👀樊梓慕:个人主页
🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》
🌝每一个不曾起舞的日子,都是对生命的辜负
目录
前言:
【LeetCode】面试题02.04. 分割链表
【LeetCode】160. 相交链表
【LeetCode】141. 环形链表
【LeetCode】142. 环形链表Ⅱ
方法一
方法二
前言:
本系列博文博主会讲解链表的经典OJ题目。
欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码:🌟fanfei_c的仓库🌟
=========================================================================
【LeetCode】面试题02.04. 分割链表
原题链接:🍏分割链表🍏
题目:给你一个链表的头节点
head
和一个特定值x
,请你对链表进行分隔,使得所有 小于x
的节点都出现在 大于或等于x
的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。
本题使用带头结点的单链表更为简单,可以免去极端情况的判断(全大于等于x或全小于x)以及连接两个链表时的麻烦。
所以我们直接申请两个哨兵结点。
- 令小于x的尾插到lead的链表上;
- 令大于或等于x的尾插到ghead的链表上。
最后连接两个链表即可。
代码实现:
struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode* ghead,*gtail,*lhead,*ltail;
struct ListNode* cur=head;
ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
if(cur->val<x)
{
ltail->next=cur;// 尾插
ltail=ltail->next;
}
else
{
gtail->next=cur;// 尾插
gtail=gtail->next;
}
cur=cur->next;
}
gtail->next=NULL;// 不置空 会导致链表进入循环
ltail->next=ghead->next;// 连接两个链表
struct ListNode* newhead=lhead->next;// 保存返回值,以便释放与返回
free(lhead);
free(ghead);
return newhead;
}
【LeetCode】160. 相交链表
原题链接:🍏相交链表🍏
题目:给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。
该题可以利用差距步的方法,首先计算两个链表的长度,利用该长度差让长的链表先走差距步。
再同时向后走,当两个指针相等时,该位置即为交点。
代码中的假设法是一种非常值得学习的方法,大家可以自行领悟,我在代码中标识出来了。
代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* curA=headA;
struct ListNode* curB=headB;
int numA=1;
int numB=1;
while(curA->next)// 题目给定链表不为空,且两个循环结束后我们需要利用cur指针来判断是否相交,所以这里采用cur->next来判断结束
{
curA=curA->next;
numA++;// 由于上面循环结束条件为cur->next为空,所以这里的值少1。因此我们定义num的值为1
}
while(curB->next)// 同上
{
curB=curB->next;
numB++;// 同上
}
if(curA!=curB)// 不相交
{
return NULL;
}
struct ListNode* longList=headA,*shortList=headB;
int gap=abs(numA-numB);// 计算差距步,abs绝对值函数
if(numA<numB)// 假设法
{
longList=headB;
shortList=headA;
}
while(gap--)// 令longList走差距步
{
longList=longList->next;
}
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
【LeetCode】141. 环形链表
原题链接:🍏环形链表🍏
题目:给你一个链表的头节点
head
,判断链表中是否有环。如果链表中存在环 ,则返回
true
。 否则,返回false
。
快慢指针法:
定义两个指针。
- 一个名为slow,slow每次走一步;
- 一个名为fast,fast每次走两步。
当fast或者fast->next不为空时持续进行指针移动。
如果该链表为环形链表,那么一定存在某一时刻slow与fast相等,返回true;
如果跳出循环证明链表为非环形链表。
代码实现:
bool hasCycle(struct ListNode *head)
{
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
【LeetCode】142. 环形链表Ⅱ
原题链接:🍏环形链表Ⅱ🍏
题目:给定一个链表的头节点
head
,返回链表开始入环的第一个节点。 如果链表无环,则返回null
。
方法一
与上面的思路相同,同样需要首先找到快慢指针相遇的时刻。
因为slow在一圈内必然fast会与其相遇,所以设slow在环内走了X距离。
设环外链表长度L,环的周长为C,slow进环时fast已经走了n圈,fast走的距离是slow走的距离的二倍,我们可以得到2(L+X)=L+n*C+X,即L=(n-1)*C+C-X。
如图:
结论:一个指针在相遇点meet,另一个指针为头指针,两指针同时移动,会在入环点相遇。
代码实现:
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
while (head != meet)
{
meet = meet->next;
head = head->next;
}
return head;
}
}
return NULL;
}
方法二
还记得上面的题目相交链表么?
我们可以将该环在相遇点meet处断开,再执行判断相交链表的函数即可。
代码实现:
//相交链表
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA;
struct ListNode* curB = headB;
int numA = 1;
int numB = 1;
while (curA->next)// 题目给定链表不为空,且两个循环结束后我们需要利用cur指针来判断是否相交,所以这里采用cur->next来判断结束
{
curA = curA->next;
numA++;// 由于上面循环结束条件为cur->next为空,所以这里的值少1。因此我们定义num的值为1
}
while (curB->next)// 同上
{
curB = curB->next;
numB++;// 同上
}
if (curA != curB)// 不相交
{
return NULL;
}
struct ListNode* longList = headA, * shortList = headB;
int gap = abs(numA - numB);// 计算差距步,abs绝对值函数
if (numA < numB)// 假设法
{
longList = headB;
shortList = headA;
}
while (gap--)// 令longList走差距步
{
longList = longList->next;
}
while (longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
//环形链表Ⅱ
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
struct ListNode* newhead = meet->next;
meet->next = NULL;
return getIntersectionNode(head, newhead);
}
}
return NULL;
}
快慢指针法是链表解题思路中非常常见的一种方法,博主在该系列博文的上一篇文章中也利用了该种方法,可以供大家整理参考,消化思路。
链接在这👉【LeetCode】【数据结构】单链表OJ常见题型(一)👈
=========================================================================
如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容
🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏+关注 ~🌟文章来源:https://www.toymoban.com/news/detail-624110.html
========================================================================= 文章来源地址https://www.toymoban.com/news/detail-624110.html
到了这里,关于【LeetCode】【数据结构】单链表OJ常见题型(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!