How would you detect a cycle in a linked list?

Detecting a cycle in a linked list is a common interview problem in computer science and it tests your knowledge on the data structure, especially linked lists, and algorithms.

Here are a couple of ways you can do this:

**1. Hashing Method**

The simplest way to detect a cycle in a linked list is by using a hash table. This method involves traversing the linked list one node at a time. For every node, check if it is in the hash table. If it is, then there is a cycle present. If the node is not in the hash table, add it and move to the next node.

Let us write the pseudo-code:

Initialize an empty hash table

For each node in the linked list:
  if the node is not in the hash table:
      add the node to the hash table
  else:
      return True  // cycle detected

return False   // cycle not detected

However, this method may not be efficient in terms of space complexity (in worst case, O(n) where n is the number of nodes).

**2. Floyd’s Cycle Finding Algorithm (Two Pointers Method)**

The second, more optimized solution involves using two pointers that traverse the list at different speeds (typically called ‘slow‘ and ‘fast‘ pointers). The ‘slow‘ pointer moves one node at a time while the ‘fast‘ pointer moves two nodes. If there is a cycle in the list, the ‘fast‘ pointer will end up looping around and meeting the ‘slow‘ pointer again. If there is no cycle, the ‘fast‘ pointer will reach the end of the list.

Let us write the pseudo-code:

Initialize slow pointer to head of the list
Initialize fast pointer to head of the list

While fast pointer is not null and fast.next is not null:
  Move slow pointer one step
  Move fast pointer two steps
  
  if slow pointer is equal to fast pointer:
    return True     // cycle detected

return False      // cycle not detected

In this method, no additional space is required, hence the space complexity is constant O(1). This algorithm is also known as the "hare and tortoise" algorithm, because of the different speeds at which the pointers traverse the list.

## Mathematical Representation

For Floyd’s cycle finding algorithm, if we assume there is a cycle, and denote the distance from the head to the cycle start as ‘x‘, the cycle length as ‘y‘, and the distance from the cycle start to the meeting point of ‘slow‘ and ‘fast‘ as ‘z‘.

When ‘slow‘ and ‘fast‘ meet, we have:

distance traveled by slow = x + z

distance traveled by fast = x + z + n ⋅ y (n is the number of laps ‘fast‘ has taken in the cycle)

Since ‘fast‘ travels at twice the speed of ‘slow‘, we get:

2 ⋅ (x + z) = x + z + n ⋅ y

Solving this, we get

x = (n − 1) ⋅ y + (y − z)

which means:

- the distance from the head of the list to the start of the cycle is equal to

- the number of complete cycle rounds the fast pointer has made minus 1 times the cycle length plus

- the cycle length minus the distance of the meeting point from the start of the cycle.

If we start two pointers again from the meeting point and the head, they will meet at the start of the cycle since the distances they have to travel are exactly the same. This can be used to find the starting point of the cycle.

Both these algorithms are useful ways to detect cycles in linked lists, and the approach you choose can depend on the specific requirements of your problem, such as whether you have space limitations.

Please note that these solutions work mainly for singly-linked lists. For doubly-linked lists, we could take advantage of the backward link to solve the problem using different approaches.