Click here to Skip to main content
16,006,348 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralRe: Function Pin
John M. Drescher8-Dec-03 9:42
John M. Drescher8-Dec-03 9:42 
GeneralRe: Function Pin
Christian Graus8-Dec-03 9:43
protectorChristian Graus8-Dec-03 9:43 
GeneralRe: Function Pin
John M. Drescher8-Dec-03 9:49
John M. Drescher8-Dec-03 9:49 
GeneralRe: Function Pin
David Crow8-Dec-03 10:19
David Crow8-Dec-03 10:19 
GeneralRe: Function Pin
John M. Drescher8-Dec-03 10:25
John M. Drescher8-Dec-03 10:25 
GeneralRe: Function Pin
Jörgen Sigvardsson8-Dec-03 13:11
Jörgen Sigvardsson8-Dec-03 13:11 
GeneralCircular linked list puzzle Pin
melwyn8-Dec-03 4:01
melwyn8-Dec-03 4:01 
GeneralRe: Circular linked list puzzle Pin
Ian Darling8-Dec-03 4:35
Ian Darling8-Dec-03 4:35 
(mmmm, smells like homework)

Given you don't know whether it is or not, I would suggest you need to have a "slow" pointer and a "fast" pointer. For each time you move the slow pointer a single node along the linked list, you move the fast pointer on two nodes.

If there is a circle, once both pointers are inside it the fast pointer will eventually "catch up" to the slow one, and they will both point at the same node (note that this isn't necessarily the "start" node of the circle, just a node within it).

If the fast pointer reaches a terminating node, then there is (obviously) no circle.

The performance characteristics aren't fantastic, but the algorithm should be sound.

--
Ian Darling
"The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
GeneralRe: Circular linked list puzzle Pin
melwyn8-Dec-03 4:57
melwyn8-Dec-03 4:57 
GeneralRe: Circular linked list puzzle Pin
Ian Darling8-Dec-03 5:16
Ian Darling8-Dec-03 5:16 
GeneralRe: Circular linked list puzzle Pin
Jörgen Sigvardsson8-Dec-03 8:04
Jörgen Sigvardsson8-Dec-03 8:04 
GeneralRe: Circular linked list puzzle Pin
Ian Darling8-Dec-03 22:19
Ian Darling8-Dec-03 22:19 
GeneralRe: Circular linked list puzzle Pin
Jörgen Sigvardsson8-Dec-03 22:27
Jörgen Sigvardsson8-Dec-03 22:27 
GeneralRe: Circular linked list puzzle Pin
melwyn9-Dec-03 5:27
melwyn9-Dec-03 5:27 
GeneralRe: Circular linked list puzzle Pin
Terry O'Nolley8-Dec-03 15:08
Terry O'Nolley8-Dec-03 15:08 
GeneralRe: Circular linked list puzzle Pin
melwyn9-Dec-03 5:16
melwyn9-Dec-03 5:16 
GeneralRe: Circular linked list puzzle Pin
Ravi Bhavnani8-Dec-03 7:11
professionalRavi Bhavnani8-Dec-03 7:11 
GeneralRe: Circular linked list puzzle Pin
Jörgen Sigvardsson8-Dec-03 8:08
Jörgen Sigvardsson8-Dec-03 8:08 
GeneralRe: Circular linked list puzzle Pin
melwyn9-Dec-03 5:21
melwyn9-Dec-03 5:21 
GeneralRe: Circular linked list puzzle Pin
melwyn9-Dec-03 5:18
melwyn9-Dec-03 5:18 
QuestionFindWindow with class name - how do I set the class name? Pin
srev8-Dec-03 3:23
srev8-Dec-03 3:23 
AnswerRe: FindWindow with class name - how do I set the class name? Pin
srev8-Dec-03 5:08
srev8-Dec-03 5:08 
AnswerRe: FindWindow with class name - how do I set the class name? Pin
Mike Dimmick8-Dec-03 5:13
Mike Dimmick8-Dec-03 5:13 
GeneralRe: FindWindow with class name - how do I set the class name? Pin
srev8-Dec-03 5:34
srev8-Dec-03 5:34 
GeneralRe: FindWindow with class name - how do I set the class name? Pin
Mike Dimmick8-Dec-03 5:45
Mike Dimmick8-Dec-03 5:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.