数据结构初阶--链表OJⅡ

前言

本篇文章承接上篇博客，继续对部分经典链表OJ题进行讲解

相交链表

先来看题目描述

思路分析

这道题我们还是首先来判断一下链表是否相交，即看两条链表的最后一个节点是否为同一个。如果不相交，则返回空，如果相交，则进行下一步。
如果两条链表相交，我们可以考虑让较长的链表走它们的长度差步，使得两条链表此时的长度一样，然后再同时走直到两条链表的节点指向同一块区域，这个节点就是相交点。

代码实现

代码实现如下

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA=headA;int lenA=0;struct ListNode* tailB=headB;int lenB=0;while(tailA){tailA=tailA->next;lenA++;}while(tailB){tailB=tailB->next;lenB++;}if(tailA!=tailB){return NULL;}int tmp=abs(lenA-lenB);struct ListNode* llisthead=lenA>lenB?headA:headB;struct ListNode* slisthead=lenA>lenB?headB:headA;while(tmp--){llisthead=llisthead->next;}while(1){if(llisthead==slisthead){break;}llisthead=llisthead->next;slisthead=slisthead->next;}return llisthead;}

环形链表

先来看题

思路分析

这道题我们采用快慢指针的思路，这样如果是环形链表，当快指针和慢指针都进入环时，快指针总能与慢指针遇到，为保证效率和可实现度，我们让快指针一次走两步，慢指针一次走一步。 如果快指针指向空且快指针的下一个节点也指向空（因为要保证快指针能一次走两步）,说明该链表并没有形成环。

代码实现

代码如下

bool hasCycle(struct ListNode *head) {if(head==NULL)return false;struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&slow&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;
}

环形链表Ⅱ

这道题是上一道题的变式，也借鉴了上一题的思路。
来看题

思路分析

我们还是按照上一题的解题思路判断链表是否形成了环。如果没有则返回空，如果是环形链表我们继续进行下一步。

在确定存在环时，此时快指针和慢指针正好相遇，实际上，此时头节点到链表进入环的节点的距离和此时快/慢指针到链表进入环的结点的距离相等。所以此时我们只需要让头指针和快/慢指针同时走到相遇时，即为我们要找的节点。

代码实现

代码实现如下

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(fast==slow){while(slow!=head){slow=slow->next;head=head->next;}return head;}}return NULL;}

复制带随机指针的链表

思路分析

这道题的本意是让我们复制一次这个链表，我们这里采用的思路是就在原有的链表上操作，1，先在每一个节点后复制一个一样的节点，2，再把所有复制出来的节点与原链表断开，3，再链接起来，这样我们就可以得到一个和原链表一摸一样的新链表了，虽然思路听起来很简单，但是想要真正弄清楚里面所有指针到底该指向哪里，同时又要避免野指针的情况出现，还是非常有难度的，下面我把操作分为三部分来讲解。

1. 在每一个节点后复制一个一模一样的节点链接起来
   首先我们可以先判断一下链表是否为空，如果为空，就直接返回空指针，否则我们按下图进行操作：（以三个节点为例）
   
   

2. 把所有复制出来的节点有原链表断开
   

3. 最后将复制出来的节点连接再一次即可。
   

代码实现

代码实现如下

struct Node* copyRandomList(struct Node* head) {if(head==NULL){return NULL;}for(struct Node* cur=head;cur!=NULL;cur=cur->next->next){struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));newnode->val=cur->val;newnode->next=cur->next;cur->next=newnode;}for(struct Node* cur=head;cur!=NULL;cur=cur->next->next){struct Node* newnode=cur->next;newnode->random=(cur->random!=NULL)?cur->random->next:NULL;}struct Node* newhead=head->next;for(struct Node* cur=head;cur!=NULL;cur=cur->next){struct Node* newnode=cur->next;cur->next=cur->next->next;newnode->next=(newnode->next!=NULL)?newnode->next->next:NULL;}return newhead;
}

以上就是本章全部内容，如有出入，欢迎大佬指正。