【初阶数据结构篇】单链表OJ题（下篇）
文章目录
须知
💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！
👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！
接上篇：【初阶数据结构篇】单链表OJ题（上篇）-CSDN博客
8. 相交链表
题目描述：
补充：
思路1：相对简单，易理解
。先分别求出两个链表的长度，让相对更长的链表走到与小链表长度相同的位置
。再循环对该链表进行判断是否存在相交链表，存在则返回true，不存在返回false
注意：里面的细节处理很重要。
8.1 示例代码：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(headA==NULL||headB==NULL)
{
return NULL;
}
ListNode* lessHead=headA;
ListNode* greathead=headB;
int count1=0,count2=0;
while(lessHead)
{
count1++;
lessHead=lessHead->next;
}
while(greathead)
{
count2++;
greathead=greathead->next;
}
if(count1>count2)
{
lessHead=headB;
greathead=headA;
while(count1-count2>0)
{
greathead=greathead->next;
count1--;
}
}
else{
lessHead=headA;
greathead=headB;
while(count2-count1>0)
{
greathead=greathead->next;
count2--;
}
}
while(lessHead&&greathead)
{
if(lessHead==greathead)
{
return lessHead;
}
lessHead=lessHead->next;
greathead=greathead->next;
}
return NULL;
}思路2：
让两个链表同时先后走，当其中任何一个链表走到空，将该链表重新置为另一个链表的头，继续往后走，（另一个链表与之相同）直至相遇，返回相遇的节点即可。
为啥正确？？？
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};9. 环形链表
题目描述：
思路：经典快慢指针算法
9.1 示例代码：
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow=head,*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
};复杂度分析
时间复杂度：O(N)，其中 N 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
空间复杂度：O(1)。
10.环形链表 ||
题目链接：
题目描述：
思路：找链表的相交节点，再将链表的相交节点与头结点同时走，相遇时就是相交链表的入口节点。
正确性
10.1 示例代码：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//快慢指针找相遇点
ListNode* slow=head;
ListNode* fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
//存在环
if(slow==fast)//相遇点
{
ListNode* pcur=head;
while(slow!=pcur)
{
slow=slow->next;
pcur=pcur->next;
}
return slow;
}
}
return NULL;
}
};11.随机链表的复制
题目链接:138. 随机链表的复制 - 力扣（LeetCode）
题目描述：
补充：
思路：在原链表基础上进行复制链表，置random指针，将复制链表与原链表断开。
11.1 示例代码：
typedef struct Node Node;
Node* BuyNode(int x)
{
Node* newnode=(Node*)malloc(sizeof(Node));
newnode->val=x;
newnode->next=newnode->random=NULL;
return newnode;
}
void AddNode(Node* head)
{
Node* pcur=head;
while(pcur)
{
Node* Next=pcur->next;
Node* newnode=BuyNode(pcur->val);
pcur->next=newnode;
newnode->next=Next;
pcur=Next;
}
}
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)
{
return NULL;
}
//原链表上复制节点
AddNode(head);
//置random指针
Node* pcur=head;
while(pcur)
{
Node* copy=pcur->next;
if(pcur->random!=NULL)
{
copy->random=pcur->random->next;
}
pcur=copy->next;
}
//将复制链表与原链表断开
pcur=head;
Node* newhead,*newTail;
newhead=newTail=pcur->next;
while(pcur->next->next)
{
pcur=pcur->next->next;
newTail->next=pcur->next;
newTail=newTail->next;
}
return newhead;
}
相信通过这篇文章你对数据结构（单链表OJ题）的有了进一步的了解。如果此篇文章对你学习数据结构与算法有帮助，期待你的三连，你的支持就是我创作的动力！！！
下一篇文章再会！！！
原文地址：https://blog.csdn.net/braveact/article/details/143898994
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！