数据结构|【数据结构】链表，看这两篇就足够了（下集，动图版）数据结构|链表|算法|C语言

文章有些难理解，如有需要请先收藏???
链表

前言
一、链表的相交
- 方法1.计数，让长的先走差值步
- 方法2.哈希表保存结点
二、环形链表
- 方法一采用哈希表映射
- 方法二插入原链表再还原
- 2.复制带随机指针的链表
总结

前言前面的学习我们已经学会了如何写单链表和带头循环双向链表
一、链表的相交 160. 相交链表
大家打开这道题就可以看到他这里要我们返回第一个相交的节点，这题有啥思路呢
方法1.计数，让长的先走差值步我们都知道当两个链表相同长度的时候，当他们一起走，走到终点的时候有可能相遇

文章图片

那么如何让他们从相同长度开始走呢，我们就得两个链表分别遍历一遍计算长度，在计算两个链表长度的差值，让长的先走差值步
代码如下

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1=0,len2=0; struct ListNode *tailA=headA; struct ListNode *tailB=headB; while(tailA) {++len1; tailA=tailA->next; } while(tailB) {++len2; tailB=tailB->next; } int gap = abs(len1-len2); if(len1>len2) {while(gap--) headA=headA->next; } else if(len1 == len2) ; else {while(gap--) headB=headB->next; } while(headB) {if(headA==headB) return headA; headA=headA->next; headB=headB->next; } return NULL; }

方法2.哈希表保存结点哈希表就简单了，从headA处遍历结点放入哈希表中，在headB中查找是否有出现，出现就返回，若没有返回NULL

class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set us; while(headA) {us.insert(headA); headA =headA->next; } //这里就能把所有节点都放入us中 while(headB) {if(us.find(headB)!=us.end()) return headB; headB =headB->next; } return NULL; } };

二、环形链表方法一采用哈希表映射环形链表
分析：如何确定链表有环，如果我们遍历他，程序在运行，他不出结果，那是链表太长了还是链表带环，我们没办法判断，所以我们可以借助上面的知识，求两个链表的相交，我们用到快慢指针来找到哪个位置是我们的公共点，这时候保存公共点的下一个结点（tmp），将当前公共点的next置成NULL，就还原成了上一道题目了，tmp和head一起走，两个点就变成了长短不相同的两条链表求第一个公共点的问题

文章图片

这里的fast一开始要fast=fast->next->next; slow=slow->next; 满足这点我们的判断条件if(fast ==slow)才不会一开始就停下来！当然如果fast走到NULL那肯定就不带环了，并且我们找两个链表的共同结点用上一题的接口就可以了

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1=0,len2=0; struct ListNode *tailA=headA; struct ListNode *tailB=headB; while(tailA) {++len1; tailA=tailA->next; } while(tailB) {++len2; tailB=tailB->next; } int gap = abs(len1-len2); if(len1>len2) {while(gap--) headA=headA->next; } else if(len1 == len2) ; else {while(gap--) headB=headB->next; } while(headB) {if(headA==headB) return headA; headA=headA->next; headB=headB->next; } return NULL; } struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL) return NULL; struct ListNode *slow,*fast; slow = fast = head; slow =slow->next; if(fast->next) fast =fast->next->next; else return NULL; //说明fast能走到NULL，那肯定不带环 while(fast &&fast->next) {if(fast ==slow) break; slow =slow->next; fast =fast->next->next; //fast指针一直比slow快，所以他们相遇表示一定带环 } if(fast ==slow) {struct ListNode *tmp =slow; tmp =tmp->next; slow->next =NULL; return getIntersectionNode(head,tmp); } else {return NULL; } }

方法二插入原链表再还原结论法：我们这里先说结论，从公共点和head开始往后走，第一个遇到的就是链表成环的第一个结点，知道这个结论之后这道题解起来可以说毫无难度，但是是为什么呢？为什么从公共点和head同时走就可以找到第一个结点呢？

文章图片

所以代码就可以改成下面：

struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL) return NULL; struct ListNode *slow,*fast; slow = fast = head; slow =slow->next; if(fast->next) fast =fast->next->next; else return NULL; //说明fast能走到NULL，那肯定不带环 while(fast &&fast->next) {if(fast ==slow) break; slow =slow->next; fast =fast->next->next; //fast指针一直比slow快，所以他们相遇表示一定带环 } if(fast ==slow) {while(slow!=head) {slow= slow->next; head= head->next; } return head; } else {return NULL; } }

2.复制带随机指针的链表复制带随机指针的链表
方法一：建立每个复制的结点和原来的节点的映射关系，用哈希map，然后我们就可以对每一个结点的random指针找到他的它对应的位置啦

class Solution {public: Node* copyRandomList(Node* head) {Node* cur =head; unordered_map um; while(cur) {Node* newnode = new Node(cur->val); um[cur]=newnode; cur = cur ->next; }//建立映射 cur = head; while(cur) {um[cur]->next=um[cur->next]; um[cur]->random=um[cur->random]; cur = cur->next; } return um[head]; } };

方法二：方法二就会稍微复杂一点点，你听我慢慢道来，首先复制结点然他们的next指针相连并不是难事，但是难在random指针，当然我们可以通过原结点与他的random指针的距离确定指向，但这样的时间复杂度就非常大了，我们想要解决这个问题，其实跟方法一一样，我们要创建原结点与拷贝结点之间的关系，所以我们先将拷贝结点放在原结点的后面

文章图片

然后我们就可以通过这种关系去找到拷贝节点的random，每一个拷贝节点的random都是前一个结点的random->next，你观察上图就能发现这个规律
代码，当然最后我们处理好每个拷贝的random指针后，要把原链表也还原回去！！

typedef struct Node Node; struct Node* copyRandomList(struct Node* head) {if(head==NULL) return NULL; Node*cur =head; while(cur) {Node* newnode=(Node*)malloc(sizeof(Node)); newnode->val = cur->val; //标记下一个位置 Node* next = cur->next; cur->next =newnode; newnode->next =next; cur =next; //完成迭代，将我们的拷贝的结点跟原有节点形成映射 } cur = head; while(cur) {//处理random指针 Node* copy=cur->next; Node*next = copy->next; if(cur->random) copy->random=cur->random->next; else copy->random =NULL; cur=next; } //将原来的链表还原和把拷贝的链表弄到 Node* newHead,* newTail; newHead=newTail=(Node*)malloc(sizeof(Node)); cur=head; while(cur) {Node*copy=cur->next; Node* next = copy->next; newTail->next = copy; newTail=copy; cur->next =next; cur=next; }Node* first =newHead->next; free(newHead); return first; }

总结 【数据结构|【数据结构】链表，看这两篇就足够了（下集，动图版）】这篇文章主要介绍了一些常见的链表的解题方法，大家如果遇到上述表述不清的话欢迎和我讨论，喜欢的话一键三连哟！！！