The Self-Taught Computer Scientist

Chapter 10 Linked Lists
111
You start with two variables, a 
fast
variable and a 
slow
variable:
slow = self.head
fast = self.head 
Then you create an infinite loop:
while True:
Inside your infinite loop, you assign the next node in the linked list to 
slow
and the node after it to 
fast
. You put this code inside a 
try
block because if the linked list is not circular, eventually 
fast
will 
be 
None
, which means you will call 
fast.next.next
on 
None
, which will cause an error. The 
try
block 
also prevents your program from failing if the input is an empty list or a noncircular list with one item.
try:
slow = slow.next
fast = fast.next.next
Next, you check to see whether 
slow
and 
fast
are the same 
object
. You are not checking whether 
the two linked list node’s values are the same because the same data could appear in more than one 
node. Instead, you use the 
is
keyword to check whether the two nodes are the same object. If they 
are the same object, you return 
True
because the linked list is circular.
if slow is fast:
return True 
If there is an error, it means you called 
.next.next
on 
None
, which means your linked list is not 
circular, and you return 
False
.
Vocabulary
linked list: An implementation of the list abstract data type.
node: A part of a data structure that contains a piece of data and can connect to other pieces of data.
pointer: The piece of data in each node that contains the location of the next node in a linked list.
head: The first node in a linked list.
singly linked list: A type of linked list with pointers that point only to the next element.