Looped logic
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while((slow != null) && (fast != null) && (slow.next != null) && (fast.next != null)){
if(slow == fast){
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}
To detect a circular linked list, we use the two-pointer technique, slow and fast.
My question is, how do I know the pointers should intersect at some point if the list is a circular list?
source to share
Look at your watch. It is a circular list of numbers 1 through 12, then circles backward by 1.
The big hand moves quickly, the small hand moves slowly while simultaneously moving in the same direction and starting from the same point (top = 12).
Since the list (edge) is circular, the large hand eventually catches the small hand. How quickly depends on the difference in speed, but it will catch up. If he catches up, the list should be round.
If it doesn't catch up but gets to the end of the list, the list is not circular.
Even if the list does not go back to the beginning, eg. if 12 was circling to 9, the fast hand just kept circling until the small hand hit the circle, and then the fast hand eventually caught up with the small hand.
Ok, for this last part, the picture of the clock was not very good, but I hope you get the idea.
source to share
The proof is not as obvious as it might seem.
In fact, with a slight change that would speed up a fast pointer, for example. using fast = fast.next.next.next
, the algorithm will no longer work.
The relative speed of the two pointers is important.
In the standard case, the relative speed is 2 - 1 = 1, which means that at each step the fast pointer gets one unit closer to the slower pointer. Thus, it is guaranteed that the fast one will catch up and not jump over the other.
Otherwise, for example, if the relative speed is 3 - 1 = 2, then they may never intersect. This happens if we start with an odd distance between pointers and the loop length is even. In this case, the distance always always remains odd (so it will never be zero).
To make it clear that pointers may not intersect if you are not careful about the speed difference, consider a fast pointer with speed 3 and a slow pointer with speed 1 running in a 4-knot loop labeled 0, 1, 2, 3, forming this loop like this 0 → 1 → 2 → 3 → 0.
Suppose initially the slow pointer is at node 0 and the fast pointer is at node 1. (note that this is not a strong assumption and cannot be mitigated by another initialization strategy - whatever the initialization method, maybe there are some additional nodes rather than part of a loop, which allows pointers to be at arbitrary positions once they both reach the loop).
After the k
steps, the slow pointer will be at node k mod 4
. The fast node will be on node (1 + 3k) mod 4
. Assuming that exists k
, so the fast and slow pointer are at the same position, that means (1 + 3k) mod 4 = k mod 4
, i.e. (1 + 2k) mod 4 = 0
... But the left side is an odd number, so it cannot be zero. Therefore, the assumption that pointers can point to the same node leads to a contradiction.
source to share
Well, as andreas mentioned, look at the watch, but if it doesn't make sense yet, this might help.
Alternatively, you can simplify your code a bit:
public boolean isCyclic(Node first) {
if(first == null) {
return false;
}
Node fast = first;
Node slow = first;
while(fast.getNext() != null && fast.getNext().getNext() != null) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if(slow == fast) {
return true;
}
}
return false;
}
- Code copied from http://codecramp.com/linked-list-loop-detection/
I also think you should initialize the pointer swift with head instead of head.next
source to share
Here is the complete implementation of a circular linked list in C:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
void insert(struct node** head,int ele){
struct node* temp = (struct node*)malloc(sizeof(struct node));
struct node* ptr;
temp->data = ele;
temp->next = temp;
if(*head == NULL){
*head = temp;
}else{
ptr = *head;
while(ptr->next != *head){
ptr = ptr->next;
}
ptr->next = temp;
temp->next = *head;
}
}
void deleteLastEle(struct node** head){
struct node* current = *head;
struct node* pre = *head;
while(current->next != *head){
pre = current;
current = current->next;
}
pre->next = current->next;
free(current);
}
void deleteAtPos(struct node** head,int pos){
struct node* current = *head;
struct node* pre = *head;
for(int i=0;i<pos-1;i++){
pre = current;
current = current->next;
}
pre->next = current->next;
free(current);
}
void deleteFirst(struct node** head){
struct node* current = *head;
struct node* temp = *head;
while(current->next != *head){
current = current->next;
}
current->next = (*head)->next;
*head = (*head)->next;
free(temp);
}
printCLL(struct node** head){
struct node* ptr = *head;
do{
printf("%d ",ptr->data);
ptr = ptr->next;
}while(ptr != *head);
printf("\n");
}
// main() function.
int main(void) {
struct node* head = NULL;
for(int i=0;i<5;i++){
//function to insert elements in linked list
insert(&head,i);
}
printf("inseted linkedlist: \n");
//print the content of linked list.
printCLL(&head);
//function to delete last element
deleteLastEle(&head);
printf("after deleting last element: \n");
printCLL(&head);
//function to delete element at pos 3.
deleteAtPos(&head,3);
printf("after deleting at pos 3: \n");
printCLL(&head);
//function to delete first element of linkedlust
deleteFirst(&head);
printf("after deleting first element: \n");
printCLL(&head);
return 0;
}
And these are the outputs:
inseted linkedlist:
0 1 2 3 4
after deleting last element:
0 1 2 3
after deleting at pos 3:
0 1 3
after deleting first element:
1 3
source to share