## 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.

```              ---------------------------------------------------------------
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.

```              ---------------------------------------------------------------
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);
}
```
Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey