Linked List Cycle

Given a linked list, determine if it has a cycle in it.

http://www.lintcode.com/en/problem/linked-list-cycle/

Discussion

设置两个指针,一个快一个慢,快 的指针每次走两步, 慢的指针每次走一步, 如果快指针和慢指针相遇, 则说明有环.

反正以我的聪明才智是想不到的,能想到用hash就不错了

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
};

results matching ""

    No results matching ""