### Linked List Cycle

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

Follow up:

Can you solve it without using extra space?

Can you solve it without using extra space?

### Analysis:

Currently the best way I can figure out is the classic two pointers.One pointer is slow (1 step a time)

One pointer is fast (2 steps a time)

If there is a cycle, the two pointers will eventually meet (equal).

### Code:

/** * 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) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (!head){return false;} ListNode* p=head; ListNode* q=head; while(q->next && q->next->next){ p=p->next; q=q->next->next; if (p==q){return true;} } return false; } };

## No comments:

## Post a Comment