Classic Linked List Problems

Reverse the list

Walk through the list and turn each arrow around. You need three pointers: the previous node, the current node, and the next node (so you don't lose the rest of the chain):

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next      # remember the rest
        current.next = prev     # turn the arrow around
        prev = current          # step forward
        current = nxt
    return prev                 # the old tail is the new head

head = reverse(Node(1, Node(2, Node(3, Node(4)))))
while head:
    print(head.value, end=" ")
    head = head.next
print()

Output

4 3 2 1 

Find the middle: slow and fast pointers

Move slow one step and fast two steps at a time. When fast reaches the end, slow is in the middle:

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.value

print(middle(Node(1, Node(2, Node(3, Node(4, Node(5)))))))

Output

3

Think of it like this: Two runners on a track, one twice as fast. When the fast one finishes, the slow one is exactly halfway.

Does the list loop back on itself?

If the last node points back into the list, walking it would never end. With slow and fast pointers, the fast one eventually laps the slow one – if they ever meet, there's a cycle:

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

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

a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
print(has_cycle(a))
c.next = a                 # make a loop
print(has_cycle(a))

Output

False
True

Tip: Slow/fast pointers (also called Floyd's tortoise and hare) solve many linked list puzzles in O(n) time and O(1) space.