# Loops in a singly linked list

[cs

challenges

]
Given a Singly Linked List, the challenge is to find out if the tail is connected to the head, i.e. if we are dealing with a loop.

The (almost) brute force solution would be to traverse the list, starting at, and save the ids of each node into a data structure like a Set. For each new node, we check if that is already stored in the set, in which case, we are dealing with a loop.

Set should be able to return if it contains a given value in *O(1)*, *O(n)* being the worst case. So, adding that to the *O(n)* time complexity of traversing the list in the first time, on average we should expect to get done in *O(n)*. Not bad.

But, what if space complexity is a problem? Then we can traverse the list with two pointers, one traveling faster than the other. If, at some point, the faster overlaps the slower, then we know we have a loop. And we don’t need to maintain a Set or a hash table to keep track of the visited nodes. And we are still at a time complexity of *O(n)* (with no risk to fall down into *O(n^2)*)

```
extension LinkedList {
func detectCycle() -> Bool {
var slow:NodeType? = self.head
var fast:NodeType? = self.head
var found = false
while slow != nil && fast != nil {
slow = slow?.next
fast = fast?.next?.next
if let s = slow, let f = fast {
if s == f {
found = true
break
}
}
}
return found
}
}
```

The entire example can fe found in the linked playground.