题目一 环形链路
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
还是先上图
我们先来看有环的情况
这个时候实际上fast和slow会在里面陷入死循环
我们把这个图再抽象下
实际上就是一个这样子的图形
大家有没有表示眼熟？
这不就是我们的操场吗
那么我们把问题变一下
两个人跑步 一个跑的比较快 一个跑的比较慢
如果在一个直线的操场上它们会相遇嘛？
显然不会
但是如果在一个环形的操场上呢？
那必然会啊
那么我们接着来看
我们证明这两个问题后，环的问题就很简单了，直接上手写代码
* struct ListNode { *int val; *struct ListNode* next; * }; */ bool hasCycle(struct ListNode* head) { struct ListNode* slow, * fast; slow = fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }
题目二 环形链表二
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
这一题跟上一题一样但又不一样
我们又要证明一个结论
我们按照这个结论写代码会非常简单
* struct ListNode { *int val; *struct ListNode* next; * }; */ struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow, * fast; slow = fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = slow; struct ListNode* start = head; while (meet != start) { start = start->next; meet = meet->next; } return meet; } } return NULL; }
还有一种不用结论的方法，找入口问题转换成找链表交点问题
* struct ListNode { *int val; *struct ListNode* next; * }; */ struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { struct ListNode* tailA = headA, * tailB = headB; int lenA = 1; int lenB = 1; //计算链表A的长度 while (tailA->next) { tailA = tailA->next; ++lenA; } while (tailB->next)//B的长度 { tailB = tailB->next; ++lenB; } int gap = abs(lenA - lenB);//长度差的绝对值 struct ListNode* longlist = headA, * shortlist = headB; if (lenA < lenB)//判断谁长谁短 { longlist = headB; shortlist = headA; } //长的先走差距步 while (gap--) { longlist = longlist->next; } //同时走 while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; } struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow, * fast; slow = fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (fast == slow) { struct ListNode* meet = slow; struct ListNode* lit1 = head; struct ListNode* lit2 = meet->next; meet->next = NULL; return getIntersectionNode(lit1, lit2); } } return NULL; }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
