给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回
null。为了表示给定链表中的环，我们使用整数
pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
进阶：
你是否可以不用额外空间解决此题？
解法一：
//时间复杂度O(n), 空间复杂度O(n)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> us;
while(head) {
if(us.count(head)) break;
us.insert(head);
head = head->next;
}
return head;
}
};//时间复杂度O(n), 空间复杂度O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !head->next) return nullptr;
ListNode *p1 = head->next, *p2 = head->next->next;
while(p1 != p2) {
p1 = p1->next;
if(!p2 || !p2->next) return nullptr;
p2 = p2->next->next;
}
p2 = head;
while(p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};解法一：
用一个哈希表us记录访问过的结点，如果当前结点在us中出现过，说明它就是入口。
解法二：
快慢指针法。p1和p2开始时都指向head，p1每次前进一步，p2每次前进两步，直到遇到空指针（此时说明无环，返回nullptr），或者相遇；p1从相遇点开始，p2再从head出发，二者都以每次一步的速度向前走，直到再次相遇，此时相遇点就是入口点。
理解上面的过程需要画图分析，分析见寻找有环单链表的入口节点。
2019/12/19 15:04