Finding Cycles and Middles
Finding cycles and middles is the task of locating a loop in a linked list and the middle node of a list. Both jobs use two walkers moving at different speeds.
The recognition signal
A problem asks for a cycle or a middle when it mentions a loop or the center of a list. The two questions below are the signals.
questions = [
"Does this list loop back on itself?",
"Which node sits in the middle of the list?",
]
for q in questions:
print("Signal: " + q)The fast and slow template
The slow walker moves one step and the fast walker moves two steps. A meeting means a cycle, and the slow walker marks the middle.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle_value(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.value
head = build([1, 2, 3, 4, 5])
print("Cycle:", has_cycle(head))
print("Middle:", middle_value(head))Worked problem: a looping list
A list of four nodes links its last node back to its second node. The walkers must meet, so the test reports a cycle.
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle_value(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.value
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
a.next = b
b.next = c
c.next = d
d.next = b
print("Cycle:", has_cycle(a))Example
class Node:
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
values = []
node = head
while node is not None:
values.append(node.value)
node = node.next
return values
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle_value(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.value
head = build([10, 20, 30, 40, 50, 60])
print("Cycle:", has_cycle(head))
print("Middle:", middle_value(head))Key points
- A cycle is a link that points back to an earlier node instead of ending the list.
- Use a slow walker and a fast walker to test for a cycle.
- The fast walker moves two steps per round while the slow walker moves one step.
- If the fast walker meets the slow walker, the list has a cycle.
- Finding cycles and middles is one skill with two jobs, both solved by walkers at different speeds.
The list has six nodes and no loop. The fast walker reaches the end after three rounds. The slow walker has moved three steps by then, so it stands on 40, the middle node.
Note
the middle node is the node the slow walker stands on when the fast walker reaches the end.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A list has nodes 1 to 7 in order and no loop. The slow walker starts at 1 and the fast walker moves twice as fast. Where does the slow walker stop?