带环链表的相关知识点

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

1.判断是否有环

方法:快慢指针追击
fast每次走两步,slow每次走一步。如果fast（或fast->next）能指向NULL,则说明无环;如果fast追击到==slow,则说明有环。

/**
* 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(slow == fast)
			return true;
	}
	return false;
}

证明：
问题1：为什么一定会相遇，有没有可能错过，然后永远追不上？

slow走一步，fast走两步，假设从slow入环后最开始两个指针相差的距离为n，随着fast的追赶距离逐步减小，最后为0说明相遇。

问题2：slow一次走一步，fast一次走两步，fast可不可以走3步、4步…?

• 假设fast走3步，那么两个指针之间距离的变化趋势为n、n-2…，即需要通过判断n的奇偶性来确定，因此就目前而言，fast走别的步数不一定，有可能错过。
• 在这个例子中，n为偶数则相遇，n为奇数则错过，开始了下一轮循环，这时fast和slow距离相当于-1，假设周长为C，如果C-1为偶数则相遇，为奇数则永远追不上。
  fast和slow可能错过吗？
  证明：
  假设fast一次走3步，slow到达环时，fast已经走了x圈并再走了C-N。
  
  可得：
  3 * L = L+x * C+C-N
  2 * L = (x+1) * C-N
  综上可得：只有当n为奇数、C为偶数时fast才会永远追不上，但从这个等式来看，这种情况不存在，所以不存在追不上的情况。

2.寻找入环节点

方法：
2.1 两个节点，一个从head走，另一个从meet走
证明：

假设fast一次走两步。
2 * slow = fast
2 * (L+N) = L+x * C+N
L+N = x * C
L = x * C-N
L = (x-1) * C+(C-N)

struct ListNode* detectCycle(struct ListNode* head){
	struct ListNode* slow = head,*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;
}

2.2 将相遇节点的下一个节点置空，这样就转换为了求链表相交节点的问题

struct ListNode* detectCycle(struct ListNode* head){
	struct ListNode* slow = head,*fast = head;
	while(fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next;

		//相遇
		if(slow == fast)
		{
			struct ListNode* meet = slow;
			struct ListNode* newhead = meet->next;
			meet->next = NULL;

			return getIntersectionNode(head,newhead);
		}
	}
	return NULL;
}

补充：相交链表

两个链表的next指向同一个节点，判断两个尾指针是否相等（地址判断）。
思路1：A链表中的节点依次与B所有节点比较，相等即交点。
O(N^2)/O(M * N)，时间复杂度过大
思路2：使长链表与短链表长度一样，一起遍历比较，相等即交点。
时间复杂度为O(N)

struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB){
	struct ListNode* curA = headA,*curB = headB;
	int lenA = 1,lenB = 1;//当下一个节点为空时不进入循环，尾结点没有被算入长度
	while(curA->next)
	{
		curA = curA->next;
		++lenA;
	}
	while(curB->next)
	{
		curB = curB->next;
		++lenB;
	}
	//尾结点不相等就是不相交
	if(curA != curB)
	{
		return NULL;
	}
	//长的先走差距步，再同时走，第一个相等就是交点
	//假设法
	int gap = abs(lenA-lenB);
	struct ListNode* longList = headA,*shortList = headB;
	if(lenB > lenA)//如果上述长短情况不符合则互换
	{
		longList = headB;
		shortList = headA;
	}
	while(gap--)
	{
		longList = longList->next;
	}
	while(longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}
	return shortList;
}