Basic Linked List Problem

[pauldepstein]

I don't understand the following code which is copied from a text. It
is the text's solution to the problem of determining if a linked list
is cyclic.

int DetermineTermination(node *head)
{
node *fast, *slow;
fast = slow = head;
while (1) {
if (!fast || !fast -> next)
return 0;
else if (fast == slow || fast -> next == slow)
return 1;
else {
slow = slow -> next;
fast = fast -> next -> next;
}
}
}

As I see it, while (1) just means while (true) and the while construct
isn't really needed.

However, the fast pointer is initially assigned to point to the same
value as the slow pointer.

So (as I see it), fast == slow will be true at the beginning, and the
value 1 will be returned.

So (as I see it), this function will simply return 1 almost always
unless the head pointer is null.

What am I missing?

In particular, I know that the text wants to implement the final else
statements -- slow = slow->next; etc. in order to update the slow and
fast pointers.

However, the final else only comes into play if fast == slow is false.


Why should fast == slow be false when fast is assigned to slow at the
beginning?


Thank you very much for your help.



Paul Epstein

 

[Siam]

I don't understand the following code which is copied from a text. It
is the text's solution to the problem of determining if a linked list
is cyclic.

int DetermineTermination(node *head)
{
node *fast, *slow;
fast = slow = head;
while (1) {
if (!fast || !fast -> next)
return 0;
else if (fast == slow || fast -> next == slow)
return 1;
else {
slow = slow -> next;
fast = fast -> next -> next;
}
}
}

As I see it, while (1) just means while (true) and the while construct
isn't really needed.

However, the fast pointer is initially assigned to point to the same
value as the slow pointer.

So (as I see it), fast == slow will be true at the beginning, and the
value 1 will be returned.

So (as I see it), this function will simply return 1 almost always
unless the head pointer is null.

What am I missing?

In particular, I know that the text wants to implement the final else
statements -- slow = slow->next; etc. in order to update the slow and
fast pointers.

However, the final else only comes into play if fast == slow is false.


Why should fast == slow be false when fast is assigned to slow at the
beginning?


Thank you very much for your help.



Paul Epstein

You are correct! There was in fact an error in the book (Programming
Interviews Exposed, it appears). You can see the corrected version of
the code on the Errata page at:
http://www.wiley.com/legacy/compbooks/programminginterview/errata.html

Siam

 

[Howard]

I don't understand the following code which is copied from a text. It
is the text's solution to the problem of determining if a linked list
is cyclic.

int DetermineTermination(node *head)
{
node *fast, *slow;
fast = slow = head;
while (1) {
if (!fast || !fast -> next)
return 0;
else if (fast == slow || fast -> next == slow)
return 1;
else {
slow = slow -> next;
fast = fast -> next -> next;
}
}
}

As I see it, while (1) just means while (true) and the while construct
isn't really needed.

That construct is often used for a loop which doesn't have an easily
predetermined condition for ending (or has multiple such conditions). It
forces the loop to continue until a break (or in this case, return)
statement. Without the while construct, it would only execute once.

However, the fast pointer is initially assigned to point to the same
value as the slow pointer.

So (as I see it), fast == slow will be true at the beginning, and the
value 1 will be returned.

Yep.

So (as I see it), this function will simply return 1 almost always
unless the head pointer is null.

Yep.

What am I missing?

Nothing. (Except perhaps a better example? )

(But is that really the entire code? From the indentation, it looks like
there might have been other code there, which was stripped. Just
checking...)

In particular, I know that the text wants to implement the final else
statements -- slow = slow->next; etc. in order to update the slow and
fast pointers.

However, the final else only comes into play if fast == slow is false.


Why should fast == slow be false when fast is assigned to slow at the
beginning?

You're correct. The code,as written, is in error. (I'm not going to try to
figure out the correction for the code, though. Maybe that would be a good
problem for you? )

-Howard

 

[Victor Bazarov]

I don't understand the following code which is copied from a text. It
is the text's solution to the problem of determining if a linked list
is cyclic.

int DetermineTermination(node *head)
{
node *fast, *slow;
fast = slow = head;
while (1) {
if (!fast || !fast -> next)
return 0;
else if (fast == slow || fast -> next == slow)
return 1;
else {
slow = slow -> next;
fast = fast -> next -> next;
}
}
}

As I see it, while (1) just means while (true) and the while construct
isn't really needed.

However, the fast pointer is initially assigned to point to the same
value as the slow pointer.

So (as I see it), fast == slow will be true at the beginning, and the
value 1 will be returned.

Right... Did the text claim the function worked? Or was it saying that
the function doesn't work, and you're supposed to fix it?

So (as I see it), this function will simply return 1 almost always
unless the head pointer is null.

What am I missing?

Nothing, AFAICT.

In particular, I know that the text wants to implement the final else
statements -- slow = slow->next; etc. in order to update the slow and
fast pointers.

However, the final else only comes into play if fast == slow is false.
Right.

Why should fast == slow be false when fast is assigned to slow at the
beginning?

I am not sure what you're asking here.

V