Linked List

1. Node: { value, next }. List: head (and often tail and size).
2. pushFront(v): node.next = head; head = node. O(1).
3. pushBack(v): with a tail pointer, tail.next = node; tail = node in O(1); without one, walk to the end in O(n).
4. insertAfter(node, v): new.next = node.next; node.next = new. Two pointer writes, O(1).
5. deleteAfter(node): node.next = node.next.next. O(1) — deleting a node requires its predecessor, which is why singly linked deletion by node reference is O(n) unless you copy the next node's value into it.
6. get(i) / search(v): start at head, follow next until index i or the value is found. O(n).
7. A dummy (sentinel) head node whose next is the real head removes special cases for inserting or deleting at position 0.

• The input is explicitly given as ListNode / head and the task is to reverse, merge, reorder, remove or detect a cycle.
• "In O(1) extra space" for a sequence problem — you must rewire pointers instead of copying to an array.
• You need O(1) insert/delete at an arbitrary known position, or an O(1) move-to-front (caches, MRU lists).
• Unknown or unbounded stream length where you never need random access.

Showing the closely related Singly Linked List visualization.

1append(v): walk to the tail; tail.next = Node(v)
2prepend(v): node = Node(v); node.next = head; head = node
3insert(v, i): walk to node i-1; node.next = prev.next; prev.next = node
4delete(v): walk until curr.value == v; prev.next = curr.next
5reverse(): prev = null; curr = head
6  while curr: next = curr.next; curr.next = prev; prev = curr; curr = next
7  head = prev

1class Node: value, next = null
2class LinkedList: head = null, tail = null, size = 0
3pushFront(v): n = Node(v); n.next = head; head = n; if tail == null: tail = n; size++
4pushBack(v): n = Node(v); if tail: tail.next = n else head = n; tail = n; size++
5insertAfter(node, v): n = Node(v); n.next = node.next; node.next = n; if node == tail: tail = n; size++
6deleteAfter(node): gone = node.next; node.next = gone.next; if gone == tail: tail = node; size--
7search(v): cur = head; while cur: if cur.value == v return cur; cur = cur.next; return null
8reverse(): prev = null; cur = head; while cur: nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; head = prev

• Losing the rest of the list by overwriting cur.next before saving it in a temporary (nxt = cur.next).
• Forgetting to update tail (or head) after inserting/deleting at the ends, leaving a stale pointer.
• Null-pointer errors on empty or single-node lists; fix with a dummy head and explicit checks.
• Deleting a node by reference in a singly linked list without its predecessor — impossible except by copying the next node's value.
• Off-by-one in fast/slow pointer loops (fast && fast.next vs fast.next && fast.next.next) when finding the middle.
• Accidentally creating a cycle when reordering nodes and never terminating the list with null.

• Iterative and recursive reversal, including reverse in groups of k and reverse between positions.
• Fast/slow pointers to find the middle, detect a cycle, and locate the cycle start.
• Two-pointer gap of k to remove the k-th node from the end in one pass.
• Merge two sorted lists with a dummy head; merge k lists with a Min-Heap.
• Dummy head sentinel to unify insert/delete at position 0 with the general case.
• Splitting and re-merging lists (reorder list, odd-even list, sort list with merge sort).