Home » Ask & Discuss » Board Exams - CBSE, ICSE, State Boards » Computer Science « Back to Discussion

Computer Science

New kid on the Block

Joined:	10 Nov 2009
Post:	3

10 Nov 2009 21:18:57 IST

0 People liked this

2427

how to check whether a linked list is circular.

None

how to check whether a linked list is circular.

Share this article on:

Comments (4)

sarang

Blazing goIITian

Joined: 20 Nov 2008

Posts: 650

10 Nov 2009 21:24:15 IST

Like 0 people liked this

not in board syllabus

Suresh Kumar

Forum Expert

Joined: 24 Aug 2009

Posts: 1342

10 Nov 2009 21:26:19 IST

Like 0 people liked this

hello dear

Create two pointers, each set to the start of the list. Update each as follows:

while (pointer1) {

pointer1 = pointer1->next;

pointer2 = pointer2->next; if (pointer2) pointer2=pointer2->next;

if (pointer1 == pointer2) {

print (\"circular\n\");

}

umesh

Forum Expert

Joined: 23 Oct 2009

Posts: 578

10 Nov 2009 21:30:57 IST

Like 0 people liked this

take two pointers temp1 and temp2
initially
temp1 = head;
temp2 = head->next->next;

while(temp1!=Null && temp2!=Null)
{
if(temp1 == temp2)
return true; //list is circular
temp1=temp1->next;
temp2=temp2->next->next;
}
return false; //list is not circular

It is somewhat difficult to get it from here, but try using this algorithm on paper ..... take 8 nodes, make it circular by conecting last node with 3rd node.
Since list is circular temp2 will move to third node from 8th node. In this case temp1 == temp2 at node 5.
Complexity of this is also very less i.e. O(2n). ~ O(n)

sushma preethi

New kid on the Block

Joined: 27 Sep 2011

Posts: 2

27 Sep 2011 09:01:05 IST

Like 0 people liked this

how to check whether a linked list is circular.

Quick Reply

Reply

	Some HTML allowed.
	Keep your comments above the belt or risk having them deleted.
	Signup for a avatar to have your pictures show up by your comment
	If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team