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

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);
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

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

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

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