- Use the runner technique. Have a slow pointer and a fast pointer. Slow pointer is always incremented by one (slow = slow.next), while fast pointer is increment twice (fast = fast.next.next).
- When the fast pointer points to null, it has reached the end of the LL, but slow pointer will be pointing to the middle node.
- Return that node.
- Runner technique (aka Floyd's cycle finding algorithm). Slow pointer and fast pointer. Slow increments by one, while fast increments twice. If the slow and fast pointer meet at any point in time, then we have found a loop. Else if, any pointer reaches the null node, we stop as there are no loops.
- In (2), we found if the linked list has a loop. That collision of the pointers could have happened anywhere within the loop. Sometimes it is useful to find where the loop starts.
- Approach: Same as before, have a slow and fast pointer and advance the fast pointer twice as fast as slow pointer till they collide.
- Now reset one of the pointers back to the start of the linked list, i.e. the head. Now advance both the slow and "fast" pointers by 1 step at the same time.
- The point at which they meet will be the start of the loop.
prev = None
curr = self.head
while(curr is not None):
next = curr.get_next()
prev = curr
curr = next
self.head = prev
def _recursive_reverse(self, node):
if(node.get_next() is None):
self.head = node
curr = self._recursive_reverse(node.get_next())
curr = node