Linked Lists

Concept

Each node holds a value and a pointer to the next node. Insertion at a known node is O(1), but reaching index i takes O(i).

Fast & slow pointers: slow moves 1 step, fast moves 2. They meet if there is a cycle, and slow is at the middle when fast reaches the end.

A dummy head node removes edge cases when the head may change.

Complexity

Code (Python)

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

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Remember

• Draw the pointers before coding.
• Use a dummy node for merges and deletions.
• Fast/slow pointers find middle and cycles.