leetcode刷题日记——环形链表

[ 题目描述 ]：

[ 思路 ]：

• 给定一个链表的头节点，判断其中是否存在环
• 可以设立两个快慢指针，快的走两步，慢的走一步，如果存在环，则总有一次，快指针一定会等于慢指针
• 如果不存在环，则链表会被走到末尾
• 运行如下
  

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {if(!head) return false;struct ListNode* fast=head;struct ListNode* slow=head;while(fast->next && fast->next->next){fast=fast->next->next;slow=slow->next;if(fast==slow) return true;}return false;
}

[ 官方题解 ]：

• 方法一：哈希表，可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
• 方法二：快慢指针，基本同上