Traverse linked list #

Traverse the entire linked list #

while head:
    head = head.next

Traverse without modifying the head #

Traverse with additional state variable #

current_node = head
while current_node:
    current_node = current_node.next

Traverse with sentinel head only #

sentinel_head = Node(None, head)
while head:
    head = head.next
return sentinel_head.next

Traverse with sentinel head and tail #

Traverse even nodes only / Skip every other node #

even_node = head
while even_node.next:
    even_node = even_node.next.next

Traverse simultaneously at different speeds #

Consistent speeds #

slow_pointer = head
fast_pointer = None
while slow_pointer.next:
    slow_pointer = slow_pointer.next
    fast_pointer = slow_pointer.next.next

Variable speed based on condition #

Comment: Variable length sliding window

Traverse with memory #

Remember if value is seen before: #

seen = set() # Why not use Python dictionary?
current_node = head
while current_node:
    if current_node.value not in seen:
        seen.add(current_node.value)
    current_node = current_node.next

Comment: Detect duplicate values

Remember node memory location (w/o duplicate values) #

memory = {} # Why not use Python set?
current_node = head
while current_node:
    if current_node.value not in memory:
        memory[current_node.value] = current_node
    current_node = current_node.next

Remember node memory location (w/ or w/o duplicate values) #

memory = {}
current_node = head
while current_node:
    if current_node.value not in memory:
        memory[current_node.value] = []
    memory[current_node.value].append(current_node)
    current_node = current_node.next

Remember the most recent node with a duplicate value #

memory = {} # Why not use Python set?
current_node = head
while current_node:
    if current_node.value not in memory:
        memory[current_node.value] = current_node
    current_node = current_node.next

Comment: Cache implementation