【初阶数据结构篇】单链表OJ题（下篇）

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

接上篇：【初阶数据结构篇】单链表OJ题（上篇）-CSDN博客

8. 相交链表

题目链接：160. 相交链表 - 力扣（LeetCode）

题目描述：

补充：

思路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. 环形链表

题目链接：141. 环形链表 - 力扣（LeetCode）

题目描述：

思路：经典快慢指针算法

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.环形链表 ||

题目链接：

142. 环形链表 II - 力扣（LeetCode）

题目描述：

思路：找链表的相交节点，再将链表的相交节点与头结点同时走，相遇时就是相交链表的入口节点。

正确性

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;
}