想法一
快慢指针,设置slow和fast指针,slow一次走一步,fast一次走两步,如果链表有环,它们最终会相遇,相遇时返回true;如果链表无环,它们最终走到空,跳出循环,返回false
bool hasCycle(struct ListNode *head) { struct ListNode *slow = head, *fast = head; while (slow && fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }
追问:1.它们一定会相遇吗?
2.如果slow一次走一步,fast一次走n步,还会相遇吗?(n>2)
问题一
问题二