Linked Lists
Slow and Fast Pointers
Can be used to find the middle or a cycle. If a cycle occurs the fast pointer will eventually meet the slow.
Find middle:
class Node:
def __init__(self, val):
self.val = val
self.next = None
def __str__(self):
return str(self.val)
print("Creating even linked list (length 4)")
# [1, 2, 3, 4]
head = Node(1)
n = head
for i in range(2, 5):
n.next = Node(i)
n = n.next
n = head
while n:
print(n.val)
n = n.next
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
print("Middle: ", slow.val)
print("Creating odd linked list (length 5)")
# [1, 2, 3, 4, 5]
head = Node(1)
n = head
for i in range(2, 6):
n.next = Node(i)
n = n.next
n = head
while n:
print(n.val)
n = n.next
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
print("Middle: ", slow.val)
Reversal
# Reverse
n = head
prev = None
while n:
# Create temp for next
nextemp = n.next
# Set next to prev
n.next = prev
# Update prev
prev = n
# Go to next node
n = nextemp
print("\nReversed linked list:")
# Last ends up as prev
n = prev
while n:
print(n.val)
n = n.next
Last updated