[TOC] ## 141 环形链表 给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 一、利用map 二、利用双指针（快慢指针） ``` class Solution { public: bool hasCycle(ListNode *head) { //-------快慢指针（12ms） //-------快指针一次走两步，慢指针一次走一步，如果链表有环，那么两个指针始终会相遇。 //-------时间复杂度 O(n)，空间复杂度 O(1) if (head == NULL) returnfalse;         ListNode* fastHead = head->next; while(fastHead != NULL && head != NULL && fastHead->next != NULL)         { if (fastHead == head) return true;             head = head->next;             fastHead = fastHead->next->next;         } return false;             } }; ``` ## 142 环形链表二 [https://leetcode-cn.com/problems/linked-list-cycle-ii/](https://leetcode-cn.com/problems/linked-list-cycle-ii/) 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -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) { /\*快慢指针。快指针一次走两步，慢指针一次走一步,当快指针和慢指针相遇时，head->环起点的地方= 相遇点fast指针 相同方向走到->环起点的地方\*/ if (head == NULL || head->next == NULL)         { return NULL;         }         ListNode* fastNode = head;         ListNode* slowNode = head; while(fastNode != NULL && fastNode->next !=NULL)         {             fastNode = fastNode->next->next;             slowNode = slowNode->next; if (fastNode == slowNode)             { slowNode = head; while(fastNode != slowNode )                 {                     fastNode = fastNode->next;                     slowNode = slowNode ->next;                 } return fastNode;             }         } return NULL;     } }; ```