Cyclic Linked List – Python function to find the node at the start of the loop
July 18, 2010 – 11:01 pmI’d blogged previously about writing a python function to find out whether a linked list is acyclic or not – it’s worth a read before tackling this one.
Problem: Given the head node of a cyclic (or circular) linked list, write a function to return the node that is at the start of the loop.
A cyclic linked list would look something like this:
A->B->C->D->E->F->C
In the case above, A is the head node, and C is the node at the start of the loop.
If the fast and slow pointers were enter the start of the loop at the same time, the fast pointer will catch up to the slow pointer when the slow pointer has gone around the loop once and is back at the start again.
If the fast pointer has a head start – that is it’s inside the loop already by the time the slow pointer gets to the start – then the fast pointer will catch up to the slow pointer before the slow pointer gets around once. In fact, it will catch up to it x nodes before the start node, where x is the number of node head start it had. So if the fast pointer is 3 nodes ahead when the slow pointer gets to the start of the loop, the fast pointer will catch up to it when the slow pointer is 3 nodes from reaching the start again.
How do we know how much head start the fast pointer had? Well, if you think about it, the length of the linked list before the start of the loop is effectively the head start the fast pointer gets (the fast pointer is always the same distance from the slow pointer as the slow pointer is from the head).
So as soon as the fast pointer catches up to the slow pointer inside the loop, we can set the slow pointer back to the head, and walk both forward a step at a time until they meet again – at the start of the loop!
def startOfCyclicLoop(head):
"""
>>> e1=Element(1)
>>> e2=Element(2)
>>> e3=Element(3)
>>> e4=Element(4)
>>> e5=Element(5)
>>> e1.next=e2
>>> print startOfCyclicLoop(e1)
None
>>> e2.next=e3
>>> e3.next=e4
>>> e4.next=e5
>>> print startOfCyclicLoop(e1)
None
>>> e5.next=e3
>>> print startOfCyclicLoop(e1)
3
>>> e5.next=e4
>>> print startOfCyclicLoop(e1)
4
>>> e5.next=e2
>>> print startOfCyclicLoop(e1)
2
"""
slow=head
fast=head
while fast!=None and fast.next!=None:
slow=slow.next
fast=fast.next.next
if (fast==slow):
slow=head
while (fast!=slow):
slow=slow.next
fast=fast.next
return fast
return None
class Element:
def __init__(self,data,next=None):
self.data=data
self.next=next
def __str__(self):
return str(self.data)
if __name__ == "__main__":
import doctest
doctest.testmod()
and the probability of tossing tails 
.
. On his 4th toss it’s 
and so on.
…
…
…
which is what we’d worked out before. For the case where the probability of tossing a head is 1/4, then we get 
, which is the probability of winning for the starter.
the length of shared highway in the middle. So the total length of the road will be:
is the shortest. So we can differentiate 
.
(where r equals the 2 year discount factor)
or 6.03%
(where r equals the 3 year discount factor)
or 7.097%
where 
is the forward rate for the second year 
is that:
represents the number of compounding periods. Given normal conventions, this is typical represented as 
where m is months (or other periods – it represents how many chunks we divide the year into for receiving interest payments) and Y is years. Also, the 
(or rate) above is normally quoted in years, so we should divide this by the months: 
.
is as high as possible, converging on 
.
and we would get:
![FV = PV * [\lim_{x\to\infty} (1+\frac{1}{x})^{x}]^{RY}](http://rebrained.com/wp-content/plugins/cache/tex_88813b227ec8bd7f83ad222d84044511.gif)
, his second toss 
, his third 
. So we can see that on his nth toss, his probability will be 
with n starting at 1. 
. 
.
with n starting at 0. Since n starts at 0, we need to get this into the form: 
. Expanding as above:
.