一.判断该链表是否有环（简单）：
1.题目
2.思路：
快慢指针 ：慢指针每走一步，快指针走两步，两个指针的起始位置都在原链表的头节点。如 果链表 带环，就一定会在环中相遇，否则快指针就先走到链表的末尾。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
{
return true;
}
}
return false;
}3.扩展问题：
(1) 为什么一定会相遇？有没有可能错过，永远追不上？
如果链表带环，那么两个指针最后都会进入环，快指针先进环，慢指针后进。
当慢指针刚进环时，最好的可能就是直接和快指针相遇，最差的情况下，两个指针的距离刚好就是换的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况。
因此：在慢指针走到一圈之前，快指针肯定能追上慢指针（相遇）。
(2) 快指针一次走3步，走四步，...n步，能追上吗？
简单分析一下快指针走三步的情况：
(3)上述是我们理论猜想出来的结果，但是实际真的存在永远追不上的情况吗？
分析：
重新总结：
二.环形链表2
1.题目
2.思路1：
我们对指针运动进行数学分析最终得到了头结点到入环节点的距离L与环形链表的关系。
分析代数式，我们得到启发：
两个指针：一个指针从链表的起始位置开始遍历链表，同时让另一个指针从判环时相遇点(meet)开始绕环运行，两个指针都是每次走一步，最终肯定会在入口节点的位置相遇。
注意：
(1)当慢指针进入环时，快指针可能已经在环中饶了x圈了，x至少为1。
因为：快指针先进环走到判环相遇点meet的位置,最后又在meet的位置于慢指针相遇。
(2)慢指针进入环后，快指针肯定会在慢指针走一圈之内追上慢指针。
因为：慢指针进入环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动前，每次他们之间的距离都缩减一步，因此慢指针进入环后，快指针肯定会在慢指针走一圈之内追上慢指针。
3.参考代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
{
struct ListNode* meet = fast;
while(head != meet)//指针相交时的位置就是入环位置
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}4.思路二
创建一个新指针newhead，指向meet的next指针，再将meet的next置为NULL。这样就变成了我们所熟悉的相交链表问题。大家可以看我的这篇题解http://t.csdnimg.cn/edNbx
参考代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//相交链表，如果相交返回相交节点，否则，返回NULL
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int n1 = 1;
int n2 = 1;
struct ListNode* curA = headA;
struct ListNode* curB = headB;
while(curA->next)
{
curA = curA->next;
++n1;
}
while(curB->next)
{
curB = curB->next;
++n2;
}
if(curA != curB)
{//尾节点不相等就不相交
return NULL;
}
//长的先走差距步，再同时走，第一个相等的就是交点
int num = abs(n1 - n2);
struct ListNode* LongList = headA;
struct ListNode* SortList = headB;
if(n1 < n2)
{
LongList = headB;
SortList = headA;
}
while(num--)
{
LongList = LongList->next;
}
while(LongList != SortList)
{
LongList = LongList->next;
SortList = SortList->next;
}
return LongList;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
{
struct ListNode* meet = fast;
struct ListNode* newhead = meet->next;
meet->next = NULL;
return getIntersectionNode(newhead,head);
}
}
return NULL;
}
