algorithm to find if a linked list is cyclic

The best way of doing it is to take two pointers. For every step taken by one pointer, move another pointer two steps. In this manner if there is no cycle in the linked list(i.e, if the list is linear), then by the time first pointer reaches mid if the list, second pointer reaches end of the list.

The following figure depicts the cycle in Single Linked List.

Linear Linked List Analysis

              ---------------------------------------------------------------
Node        : 1->200 | 2->300 | 3->400 | 4->500 | 5->600 | 6->700 | 7->NULL |
              -------------------------------------------------------------
Node Address: 100    | 200    | 300    | 400    | 500    | 600    | 700     |
              ---------------------------------------------------------------
Iteration-1 : p1     |        | p2     |        |        |        |         |
              ---------------------------------------------------------------
Iteration-2 :        | p1     |        |        | p2     |        |         |
              ---------------------------------------------------------------
Iteration-3 :        |        | p1     |        |        |        | p2      |
              ---------------------------------------------------------------

If you notice by the time the first pointer reaches mid of the list, second pointer has reached end of the list.

Cyclic Linked List Analysis

              ---------------------------------------------------------------
Node        : 1->200 | 2->300 | 3->400 | 4->500 | 5->600 | 6->700 | 7->300  |
              -------------------------------------------------------------
Node Address: 100    | 200    | 300    | 400    | 500    | 600    | 700     |
              ---------------------------------------------------------------
Iteration-1 : p1     |        | p2     |        |        |        |         |
              ---------------------------------------------------------------
Iteration-2 :        | p1     |        |        | p2     |        |         |
              ---------------------------------------------------------------
Iteration-3 :        |        | p1     |        |        |        | p2      |
              ---------------------------------------------------------------
Iteration-3 :        |        |        | p2  p1 |        |        |         |
              ---------------------------------------------------------------

If you notice both the pointers are referring to the same node.

Steps to solve this Algorithm:
– For every step taken by one pointer, move another pointer two steps.
– Continue this till either second_pointer/second_pointer’s next pointer is same as that of the first pointer which means second pointer has come behind the first pointer resulting in a cycle.

Source Code

	public static boolean findCylicSLL(Node root) {
		if(root == null) {
			return false;
		}
		Node ptr1 = root;
		
		Node ptr2 = root.next.next;
		while(ptr1 != null && ptr2 != null) {
			 if(ptr2 == ptr1 || ptr2.next == ptr1) {
				 return true;
			 }
			 ptr1 = ptr1.next;
			 ptr2 = ptr2.next.next;
		}
		
		return false;
	}

A small change in this same logic will lead us to another important trick:
How do you find exact middle element of the list in O(n/2) complexity?

Steps to solve this Algorithm:
– For every step taken by one pointer, move another pointer two steps.
– Continue this till either second_pointer is null which means it reached end of the list and therefore first_pointer will be exactly in the middle of the list

	public static boolean findMiddleElementOfList(Node root) {
		if(root == null) {
			return false;
		}
		Node ptr1 = root;
		Node ptr2 = root.next.next;
		
                while(ptr2 != null) {
	            ptr1 = ptr1.next;
		    ptr2 = ptr2.next.next;
		}
		
                // When ptr2 is null, it means ptr1 reached mid of the list
                System.out.println("ptr1: "+ptr1);
	}