LeetCode — Linked List Problem-Solving Notes

LeetCode — Linked List Problem-Solving Notes¶

The most basic linked list structure looks like this:

class ListNode:    def __init__(self, x):        self.val = x        self.next = None

A class called ListNode that can hold one or more values (in the example above, a single value val, initialized from x).

Each position in the list is called a node. By convention, .next points to the memory address of the next node — like a line of elementary school kids with their hands on each other's shoulders: you can see where the next person is.

One common problem type tests how to re-point references. For example, given 1->2->3, if you want to remove the even-numbered nodes, you need to save 1's .next, then get 3, and re-point to it.

Another special problem type checks whether a cycle exists — i.e., whether following .next endlessly would go on forever. The classic solution uses two pointers — slow and fast. slow advances one node at a time; fast advances two. If a cycle exists, fast will eventually catch up to slow. Example:

slow, fast = head, head  while fast and fast.next:      slow=slow.next      fast=fast.next.next      if slow==fast:          return True  return False

Most remaining problem types are variations on these patterns. The ones I tend to forget:

• Edge case: if the input starts with a null node, remember to handle it.
• Re-ordering problems: in some cases, the .next of the final node in the answer already has a value at the start — so you need to explicitly reassign .next = None at the end.