Linked List Cycle-Leetcode Solution
Que:- Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Solution - 1
# Approach
We will iterate through the whole linkedlist and find the node whose next pointer is
pointing to head. if the current node in not pointing to the head then we will change
its next pointer to next==head (in the code prev->next=mini).so, whenever we will visit
that node again, this condition will become true:-
if(curr->next==mini)
return true;
# Complexity
- Time complexity: O(N)
- Space complexity: O(1)
# 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) {
if(head==NULL || head->next==NULL)
return false;
ListNode *curr = head;
ListNode *prev = NULL;
ListNode *mini = head;
while(curr!=NULL)
{
if(curr->next==mini)
return true;
prev = curr;
curr = curr->next;
prev->next = mini;
}
return false;
}
};
Solution - 2
# Approach
Here I have used TortoiseHare Method to Detect the Cycle in the LinkedList.
# Complexity
- Time complexity: O(N)
- Space complexity: O(1)
# 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) {
if(head==NULL)
return false;
ListNode *slow = head;
ListNode *fast = head;
while(fast!=NULL && fast->next!=NULL)
{
slow = slow->next;
fast = fast->next->next;
if(fast==slow)
return true;
}
return false;
}
};
```
One more Problem is there which you can solve with the TortoiseHare Method. Visit the
link for the problem with a complete solution:- Link
Keep Learning, Keep Growing!
If you like this post then like it and share it with your friends.
Comments
Post a Comment