首页 > 代码库 > Linked List Cycle(11)

Linked List Cycle(11)

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

Follow up:
Can you solve it without using extra space? 

怎样判断一个链表之中是否有环?可以利用快慢指针的方法。定义两个指针fast和slow,两者都是从head出发,fast指针每次比slow多走一位。如果两个指针相遇了,很明显,链表中一定有环。

要注意一下循环的边界条件。什么时候停止循环,得出链表中没有环的结论。快指针走得快,当其指向为null时说明走到了终点,这没有错。但是,请注意还有一个停止循环的条件,那就是fast的下个指针指向为null时,也会造成循环结束。首先,如果fast->next为null的话,那么fast->next->next就没有意义了。而且,如果fast->next为null也能够说明链表中没有环。

上代码:

/** * 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) {        ListNode *fast,*slow;        fast=slow=head;        while(fast&&fast->next){            slow=slow->next;            fast=fast->next->next;            if(fast==slow)                return true;        }        return false;    }};

 

Linked List Cycle(11)