C语言入土之路|[数据结构]题海啊，全是水（四）相交链表、环形链表、环形链表II 快乐到家。|数据结构|c语言|链

这个是一个目录哦

相交链表
- 你说的链表，它相交吗？
- 交啊，交在哪啊？
- 代码
环形链表
- 分析
- 代码
环形链表II
- 分析比啥都重要
- 代码
最后

C语言入土之路|[数据结构]题海啊，全是水（四）相交链表、环形链表、环形链表II

文章图片

菜鸡大学生的数据结构——刷题篇4
链表刷题最后一篇，好耶！
再写下去菜鸡大学生要编不出前言了，或许本来就不需要前言？
啊——

文章图片

相交链表给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

文章图片

这道题简单来说就两个思路：

是否相交？
如果是，交点在哪？

我们先来解决第一个问题。
你说的链表，它相交吗？一说相交，可能有些人的想法是这样的：

文章图片

它雀食相交，但它不是链表。哪家链表相交节点的next节点有俩的？
我们以示意图为主。

文章图片

根据图片分析，相交链表从相交节点往后是完全一样的。哪怕是最极端的情况，最后一个节点肯定是共用的，也就是说，我们只要判断两个链表最后一个节点是不是相等即可。
交啊，交在哪啊？我也不知道啊。
要是这俩链表一样长就好了。
那么有没有办法能让它变得一样长呢？
有，快慢指针。

统计一下链表长度，算出它们的差k。
快指针先走k步。
两个指针一起走，直到指向同一节点。

文章图片

完成！
代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode * head1=headA; struct ListNode * head2=headB; int l1=1; int l2=1; while(head1->next) { head1=head1->next; ++l1; } while(head2->next) { head2=head2->next; ++l2; }if(head1!=head2) { return NULL; }head1=headB; head2=headA; if(l1>l2) { head1=headA; head2=headB; }int k=0; if(l1>l2) { k=l1-l2; } else { k=l2-l1; }while(k--) { head1=head1->next; } while(head1&&head2) { if(head1==head2) return head1; head1=head1->next; head2=head2->next; } return NULL; }

环形链表给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。

文章图片

分析这道题的解法是快慢指针。
快指针走一步，慢指针走两步。

如果不带环，快指针遍历结束，就返回NULL。
如果带环，当慢指针进入环的时候，每走一次，快慢指针之间的距离会缩小一。总会被追上。

思考题：如果快指针走三步，四步，甚至n步呢？
以三步为例：
我们假设进环时快慢指针距离为n。
那么第一次走距离就是n-2.

如果n为偶数，那么最后距离为0，能够追上。
如果n为奇数，那么最后距离为-1，快指针反超了慢指针，此时两指针的距离是环的长度-1，又要分两种情况：
1. 环的长度-1是偶数，那就可以追上。
2. 是奇数，就永远追不上了。

3倍甚至n倍同理，再说了，三倍的代码哪有二倍的好写，为什么要给自己找事情呢？（瘫）

文章图片

代码

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

环形链表II 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
翻译：在上一题的基础上找到入环节点。
分析比啥都重要

文章图片

假设：

链表头 - 入口点 —— L
入口点- meet —— X
环的长度 —— C

由于不知道环的大小，所以在相遇的时候fast指针可能已经走了N圈，所以fast指针走过的距离：L+N*C+X.
slow走过的距离L+X.
fast的距离是slow的两倍。
可得L+N*C+X=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(meet!=head) { meet=meet->next; head=head->next; } return meet; } } return NULL; //虽然没什么用但是要让编译器知道所有的情况都有返回值 }

最后 【C语言入土之路|[数据结构]题海啊，全是水（四）相交链表、环形链表、环形链表II】还有亿篇就写完了！加油啊！写博客的小妹妹！