21
- 这个题是leetcode上很经典的一道链表题
- 看到环我们就要想到快慢指针
- 两个指针，一个fast每次走两步，一个slow每次走一步
- 如果有环的话，fast一定会先进入环，slow后进入环，两个指针都进入环后继续循环一定会相遇
- 同理，相遇则证明环存在，此题已经解决
- 时间复杂度O(n)，空间复杂度O(1)
- 当然你也可以采用暴力做法，遍历然后记录每个出现的结点，如果结点再次出现，则证明有环。这样的时间复杂度为O(n)，空间复杂度也是O(n)
bool isLoop(LNode *head) { // 1.快慢指针，快的一次走两步 LNode *fast = head, *slow = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; // 两指针相遇 } // 2.没有环的情况 if (slow == NULL || fast->next == NULL) { return false; } return true; } 复制代码
- 但是通常要求不会那么简单，一定是让你返回环的入口点
- 涉及到入口点，我们就要来算一道数学题
- 假设环内一共有r个元素，链表头结点到环入口点有a个结点，环入口点到相遇点的距离为x（顺时针），快指针已经绕了n圈
- 则有
a+nr+x = 2(a+x)，解得a = nr-x - 因此设置一个指针指向head，一个指向相遇点，同步移动，相遇点即为入口点
- 时间复杂度O(n)，空间复杂度O(1)
LNode* findLoopStart(LNode *head) { // 1.快慢指针，快的一次走两步 LNode *fast = head, *slow = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; // 两指针相遇 } // 2.没有环的情况，返回NULL if (slow == NULL || fast->next == NULL) { return NULL; } // 3.两个指针分别指向头结点和相遇点 LNode *p1 = head, *p2 = slow; while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; }
