数据结构与算法⑥(第二章OJ题，下)后八道链表面试题（上）:https://developer.aliyun.com/article/1513360
代码：
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { struct ListNode* tailA = headA; struct ListNode* tailB = headB; int lenA = 1, lenB = 1; while (tailA->next) { tailA = tailA->next; lenA++; } while (tailB->next) { tailB = tailB->next; lenB++; } if (tailA != tailB) { return NULL; } int gap = abs(lenA - lenB); //gap 差值 abs求整数绝对值函数 头文件：stdlib.h while (gap--) { if (lenA > lenB) { headA = headA->next; } else if (lenB > lenA) { headB = headB->next; } } while (headA != headB)//注意不能比较next又返回next（可能为空）血的教训 { headA = headA->next; headB = headB->next; } return headA; }
评论区大诗人的代码：
（程序猿的浪漫）笑
//朋友们，请一定要珍惜身边的那个 ta 啊！你们之所以相遇，正是因为你走了 ta 走过的路， //而 ta 也刚好走了你走过的路。这是何等的缘分！ //而当你们携手继续走下去时，你会慢慢变成 ta 的样子，ta 也会慢慢变成你的样子。 class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) { return NULL; } ListNode *you = headA, *she = headB; while (you != she) { // 若是有缘，你们早晚会相遇 you = you ? you->next : headB; // 当你走到终点时，开始走她走过的路 she = she ? she->next : headA; // 当她走到终点时，开始走你走过的路 } // 如果你们喜欢彼此，请携手一起走完剩下的旅程（将下面这个 while 块取消注释）。 // 一路上，时而你踩着她的影子，时而她踩着你的影子。渐渐地，你变成了她，她也变 //成了你。 /* while (she) { you = she->next; she = you->next; } */ return you; } };
9. 判断链表中是否有环
141. 环形链表
难度简单
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置
（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 10^4]
- -10^5 <= Node.val <= 10^5
- pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { }
暴力求解代码：
自己按照给的范围取巧写的代码：
看完别人的快慢指针和证明又是震惊的一天
bool hasCycle(struct ListNode* head) { struct ListNode* head1 = head, * head2 = head; int x = 10000, y = 10000; while (x-- && head1 && head2) { while (y-- && head2) { if (head2->next == head1) { return true; } head2 = head2->next; } head1 = head1->next; if (head2) { head2 = head; } } return false; }
快慢指针代码：
就是在环里，下面走两步的快指针一定会追上慢指针
bool hasCycle(struct ListNode* head) { struct ListNode* fast = head, * slow = head; while (fast && fast->next) { if (fast->next == slow) { return true; } slow = slow->next; fast = fast->next->next; } return false; }
为什么fast一定会和slow相遇呢？
为什么fast要走两步，slow走一步呢？
面试的时候不会让写代码，但会问下面的两个延伸问题
（图片拼起来的，看不清楚的话点开放大看吧，很重要）
10. 返回链表入环的第一个节点
142. 环形链表 II
难度中等
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围 [0, 10^4] 内
- -10^5 <= Node.val <= 10^5
- pos 的值为 -1 或者链表中的一个有效索引
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { }
公式+快慢指针代码：
首先要知道，根据上面的距离的递减，fast在slow进环后最多走两圈，slow最多走一圈。
fast就会追上slow。
以下是公式推导证明
所以根据公式L = (N - 1) * C + C * X
得出结论：一个指针从相遇点开始走，一个指针走表头开始走，他们会在环的入口点相遇。
（L是一个指针从表头开始走到入口点的距离，C * X 是相遇点往后走到表头的距离，相等，就相遇。)
struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* fast = head, * slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (fast == slow) { struct ListNode* meet = slow; while (meet != head) { meet = meet->next;//一个指针从相遇点走 head = head->next;//一个指针从头走 } return meet;//会在入环的第一个节点相遇 } } return NULL; }
另一种方法：转化成链表相交
如果要求不破坏链表长度，可以让head当尾，meet当头
数据结构与算法⑥(第二章OJ题，下)后八道链表面试题（下）:https://developer.aliyun.com/article/1513376
