Circular linked list logic

Question

/**
 * 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;
    }
}

For detecting a circular linked list, we use the 2 pointer technique, slow and fast.

My question is, how do I know the pointers must intersect at some point if the list is a circular list?

Answer 1

Here is the complete implementation of 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 

Answer 2

The proof is not as obvious as it might seem.

Actually, with a little change that would make the fast pointer even faster, e.g. using fast = fast.next.next.next, the algorithm is no longer guaranteed to work.

What matters is the relative speed of the two pointers.

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 slow pointer. In this way, it is guaranteed that the fast one will catch up and not jump over the other.

Otherwise, e.g. if the relative speed is 3 - 1 = 2, then it is possible for them to never intersect. This would occur if we start with an odd distance between the pointers, and the cycle length is even. In this case, the distance always will always remain odd (thus it will never be zero).

---

To make it clear that the pointers may not intersect if not being careful about the speed difference, consider a fast pointer with speed 3, and a slow pointer with speed 1, running in a cycle with 4 nodes, labeled 0, 1, 2, 3, forming a cycle like this 0 -> 1 -> 2 -> 3 -> 0.

Assume that 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 may not be alleviated by a different initialization strategy -- regardless of the initialization method, it might be the case that there are some additional nodes in the graph, not part of the cycle, making it possible for the pointers to be in arbitrary positions once they both reach the cycle).

After k steps, the slow pointer will be at node k mod 4. The fast node will be at node (1 + 3k) mod 4. Assuming there is a k such that the fast and slow pointer are at the same position, it means (1 + 3k) mod 4 = k mod 4, i.e. (1 + 2k) mod 4 = 0. But the left hand side is an odd number, thus it can not be zero. Therefore, the assumption that the pointers can point at the same node lead to a contradiction.

Answer 3

Well, as andreas mentioned look at the watch but if that still doesn't make sense make this could help.

Also, 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 that you should initialize your fast pointer with head instead of head.next

Answer 4

Look at a watch. That is a circular list of numbers 1 to 12 then circles back to 1.

The big hand is moving fast, the small hand is moving slow, both moving in the same direction, and starting at the same point (top = 12).

Because the list (edge) is circular, the big hand will eventually catch back up to the small hand. How quickly depends on the speed difference, but it will catch up. If it catches up, the list must be circular.

If it doesn't catch up, but gets to end of list, the list is not circular.

Even if the list doesn't circle back to the beginning, e.g. if 12 circled back to 9, the fast hand would just keep circling, until the small hand enters the circle, and then the fast hand will eventually catch up to the small hand.

Ok, for that last part, the image of a watch wasn't good, but I hope you got the point.