hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Linked List Cycle
Problem: 141. Linked List Cycle
Problem Link:
Companies Asked: Deutsche Bank, Visa, Amazon, Oracle, Google, Spotify, Microsoft, Goldman Sachs
Approach:
Declare a slow and a fast pointer.
The slow pointer moves 1 step each time and the first pointer moves 2 steps each time.
Keep traversing until the slow pointer meets the first pointer.
If the fast pointer accesses a NULL node that means the list does not have any cycle. Hence return false.
Return true at the end.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
/**
* 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) {
if(!head || !head->next) return false;
ListNode *slow = head, *fast = head->next;
while(slow!=fast){
slow = slow->next;
fast = fast->next;
if(!fast) return false;
fast = fast->next;
if(!fast) return false;
}
return true;
}
};