Nodes linked by pointers. No index access — must traverse. Master reversal, cycle detection, and dummy nodes.
curr.next = prev before saving curr.next, you lose the rest of the list forever.def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
fast will crash when fast.next.next is accessed on a node with null next.class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next # Reverse — O(n), O(1) space def reverse_list(head): prev, curr = None, head while curr: nxt = curr.next # 1. save next curr.next = prev # 2. flip pointer prev = curr # 3. advance prev curr = nxt # 4. advance curr return prev # prev = new head # Dummy node trick — head might change dummy = ListNode(0) dummy.next = head curr = dummy # ... do operations ... return dummy.next # new head
# Find middle of linked list slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # slow = middle node # Kth from end — move fast k steps first def kth_from_end(head, k): fast = slow = head for _ in range(k): fast = fast.next while fast: slow = slow.next fast = fast.next return slow