本文共 1606 字,大约阅读时间需要 5 分钟。
(转自:)
如果链表有环,那么在遍历链表时则会陷入死循环,利用这个特征,我们可以设计这样的算法。
我们假定链表头到环入口的距离是len,环入口到slow和fast交汇点的距离为x,环的长度为R。slow和fast第一次交汇时,设slow走的长度为:d = len + x,而fast走的长度为:2d = len + nR + x,(n >= 1),从而我们可以得知:2len + 2x = len + nR + x,即len = nR - x,(n >= 1),于是我们可以得到这样的算法。
inter指针在遍历过程中可能多次(n >= 1)经过环入口节点,但当cur指针第一次达到入口节点时,inter指针此时必然也指向入口节点。
/** * 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) { if (NULL == head) return NULL; ListNode * fast = head; ListNode * slow = head; while (1) { fast = fast->next ? fast->next : NULL; if (NULL == fast) break; fast = fast->next ? fast->next : NULL; if (NULL == fast) break; slow = slow->next; if (slow == fast) break; } if (NULL == fast) return NULL; ListNode * cur = head; ListNode * inter = slow; while (cur != inter) { cur = cur->next; inter = inter->next; } return cur; }};