 |  |  |  |  |  |  |  |
To find whether Single Linked List is looped.
 |
•
•
Join Date: Jun 2006
Posts: 89
Reputation: 
Solved Threads: 3
Junior Poster in Training
Hi all,
What is the effficient way to check whether a single linked list is looped somewhere.The number of nodes in the list is not known.
In that case traversal of SLL will go into an infinite loop.
One solution I have is to store each address of node in array and compare the nest address with the address in the array. But this solution will be of order O(n*n). Can somebody give me an efficient solution.
What is the effficient way to check whether a single linked list is looped somewhere.The number of nodes in the list is not known.
In that case traversal of SLL will go into an infinite loop.
One solution I have is to store each address of node in array and compare the nest address with the address in the array. But this solution will be of order O(n*n). Can somebody give me an efficient solution.
For a discussion of detecting cycles in linked lists, see http://ostermiller.org/find_loop_sin...nked_list.html
-bobd-
-bobd-
|
Similar Threads
- Single Linked Circular Link List (Java)
- radix sort using queue and linked list (C++)
- Linked List & Objects (C++)
- "doubly linked list" question (C)
- help by sorting a simply linked list (C)
Other Threads in the C Forum
- Previous Thread: basics of OOP
- Next Thread: DirectSound WAVEFORMATEX Problem
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest C Posts
- Today's Posts
- Unanswered Threads
adobe api array arrays binarysearch calculate char cm convert copyanyfile copypdffile cprogramme createcopyoffile createprocess() csyntax directory dynamic feet fflush file floatingpointvalidation fork forloop frequency getlasterror givemetehcodez global graphics gtkgcurlcompiling hacking hardware highest homework i/o ide inches incrementoperators intmain() iso kernel kilometer km linked linkedlist linux linuxsegmentationfault list locate logical_drives loopinsideloop. match matrix microsoft motherboard mqqueue mysql oddnumber odf open opensource openwebfoundation owf pattern pdf performance pointer posix power probleminc program programming pyramidusingturboccodes read recursion recv recvblocked repetition research scanf scheduling segmentationfault send shape socketprograming socketprogramming stack standard strchr string suggestions systemcall test unix urboc user variable voidmain() wab win32api windows.h
