题解 | #判断链表中是否有环#
判断链表中是否有环
https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { // 快慢指针 if(head == nullptr || head->next == nullptr) return false; ListNode *fast = head, *slow = head; // 第一次相遇 do while / while do{ if((fast == nullptr) || (fast->next == nullptr)) return false; fast = fast->next->next; slow = slow->next; }while(fast != slow); // 如果相遇 return true; // fast = head; // while(fast != slow){ // slow = slow->next; // fast = fast->next; // } // return fast; } };
快慢指针!
分两步:
第一次相遇:
fast 每次走两步
slow 每次走一步
第二次相遇:
fast slow每次都只走一步