The Self-Taught Computer Scientist

Data Structures
110
First, you use a 
while
loop to iterate through your linked list, using the variables 
current
and 
previous
to keep track of the current node and the previous node.
Inside your 
while
loop, first you assign 
current.next
to the variable 
next
so that you save that 
data when you assign 
current.next
to 
previous
in the next line. Once you’ve set 
current.next
to 
previous, you’ve reversed the pointer for that node.
next = current.next
current.next = previous
Then, all you have to do is set 
previous
to 
current
and set 
current
to 
next
to continue iterating 
through your linked list and changing the rest of the pointers:
previous = current
current = next
Once you’ve changed all your pointers, you set 
self.head
to 
previous
. The reason you set the head 
to 
previous
and not 
current
is because once you’ve made it to the end of your linked list, 
current
will be 
None
, and 
previous
will contain what used to be the last node in your linked list, which you 
turn into the first node when you set it to your list’s head.
Finding a Linked List Cycle
Earlier, you learned that the last element points back to the list’s head in a circular linked list (see 
Figure 10.6). Another common interview question is to detect whether a linked list contains a cycle. 
In other words, you are checking whether the last item in the list points to any item in the list instead 
of having 
None
as its value for its “next” variable. One algorithm for detecting a linked list cycle is 
called the 
tortoise- and- the- hare algorithm. In the algorithm, you iterate through your linked list at two 
different speeds, keeping track of nodes in a 
slow
variable and a 
fast
variable. If the linked list is a 
circle, eventually the 
fast
variable will lap the 
slow
variable, and both variables will be the same. If 
that happens, you know the linked list is circular. If you reach the end of your linked list without it 
happening, you know it does not contain a cycle.
Here is how you implement a tortoise- and- the- hare algorithm:
def detect_cycle(self):
slow = self.head
fast = self.head
while True:
try:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
except:
return False

---