 |  |  |  |  |  |  |  |
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 ansi api array asterisks binarysearch calculate centimeter char character cm convert copyanyfile copyimagefile copypdffile cprogramme createcopyoffile createprocess() csyntax directory feet fflush fgets file floatingpointvalidation fork frequency function getlasterror getlogicaldrivestrin givemetehcodez global graphics gtkgcurlcompiling gtkwinlinux hacking highest homework i/o inches infiniteloop interest intmain() kilometer km linked linkedlist linux linuxsegmentationfault list locate logical_drives match meter microsoft mqqueue mysql number oddnumber odf open opendocumentformat openwebfoundation owf pattern pdf performance posix power probleminc program programming pyramidusingturboccodes read recv recvblocked repetition scanf scheduling segmentationfault send single socketprograming socketprogramming stack standard strchr string suggestions systemcall unix urboc user variable voidmain() wab whythiscodecausesegmentationfault win32api windows.h