带环链表的相关知识点

1.判断是否有环
2.寻找入环节点
- 补充：相交链表

如果链表中有某个节点,可以通过连续跟踪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;
}