Linked Lists
A linked list stores values in nodes; each node points to the next one. There is no random access, but insertion and deletion at a known node are O(1).
linked_list.py
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def from_list(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.value)
head = head.next
return out
Reverse a list
reverse.py
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
Detect a cycle (Floyd)
cycle.py
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False # O(n) time, O(1) space
Find the middle
Move fast two steps for every one step of slow; when fast reaches the end, slow is at the middle.
Loading Comments...