Linked Lists: From Zero to Interview-Ready

What Is a Linked List?

A linked list is a sequence of nodes. Each node holds a value and a pointer to the next node. That's it. No contiguous memory, no indices — just a chain of references.

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

This simple structure has surprising depth. Linked list problems test your ability to manipulate pointers carefully — one wrong reassignment and you've lost part of the list forever.

When linked lists beat arrays:

• O(1) insert/delete at the head (no shifting)
• Dynamic size without reallocation
• Efficient for implementing stacks, queues, and LRU caches

When arrays beat linked lists:

• O(1) random access by index (linked lists are O(n))
• Better cache performance (contiguous memory)
• Less overhead per element (no extra pointer per node)

The Three Pointer Technique

Most linked list operations require tracking multiple nodes simultaneously. The most common pattern is three pointers: prev, curr, and next. This is the foundation of reversal and relinking operations.

Before touching any code, draw the list on paper. Label each pointer. Then walk through what happens step by step. This prevents the most common mistake: reassigning a pointer before saving the reference it was pointing to.

Must-Know Operation 1: Traversal

Simple but foundational. Walk through every node:

def traverse(head):
    curr = head
    while curr:
        print(curr.val)
        curr = curr.next

Always check for None/null. An empty list (head is None) is a valid input in almost every problem.

Must-Know Operation 2: Reversal

The most commonly asked linked list operation in interviews.

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next  # save before overwriting
        curr.next = prev       # reverse the pointer
        prev = curr            # move prev forward
        curr = next_node       # move curr forward

    return prev  # prev is now the new head

Walk through this with a 3-node list until it's automatic. The order of operations matters: always save next_node before overwriting curr.next.

Recursive reversal is also worth knowing for interviews where they ask you to do it recursively — but the iterative version above is more reliable under pressure.

Must-Know Operation 3: Finding the Middle

Use fast and slow pointers. The slow pointer moves one step at a time; the fast pointer moves two. When fast reaches the end, slow is at the middle.

def find_middle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

For even-length lists, this returns the second middle node. If you need the first middle, add a prev pointer and track it one step behind slow.

This same fast/slow pattern is used in cycle detection, finding the k-th node from the end, and palindrome checking.

Must-Know Operation 4: Cycle Detection (Floyd's Algorithm)

Given a linked list, determine if it has a cycle. A naive approach uses a hash set — O(n) space. Floyd's algorithm does it in O(1) space.

def has_cycle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Why it works: If there's a cycle, the fast pointer will lap the slow pointer inside the cycle. They're guaranteed to meet. If there's no cycle, fast will reach the end (None) and the loop terminates.

Finding the cycle start (harder variant): After detecting the meeting point, reset one pointer to the head and move both one step at a time. Where they meet again is the cycle start. This is a beautiful mathematical property of the algorithm.

Must-Know Operation 5: Merging Two Sorted Lists

Merge two sorted linked lists into one sorted list. This is a building block for merge sort on linked lists.

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    curr.next = l1 if l1 else l2
    return dummy.next

The dummy node trick appears constantly. Instead of handling the edge case of the initial empty result separately, create a dummy head to build from. Return dummy.next at the end.

The Dummy Node Pattern

Whenever you're building a new list or might need to delete the head node, use a dummy:

dummy = ListNode(0)
dummy.next = head
# ... perform operations using dummy as anchor
return dummy.next

This simplifies edge cases dramatically. Without it, you have to handle "what if the head is the node I need to delete?" as a special case.

Common Interview Problems and How to Approach Them

Remove Nth Node From End:

Use two pointers with a gap of N. Advance the first pointer N steps ahead. Then move both until the first hits the end. The second pointer is at the node to remove. Use a dummy head to handle removing the actual head.

Palindrome Linked List:

Find the middle, reverse the second half in-place, compare both halves from their respective starts. O(n) time, O(1) space.

Reorder List:

Find the middle, reverse the second half, merge the two halves alternately. Three separate operations, each one you already know.

LRU Cache:

Combine a doubly linked list (for O(1) remove/move-to-front) with a hash map (for O(1) lookup). This is a classic system design + linked list hybrid problem.

The Mental Checklist for Linked List Problems

Before writing a single line of code:

1. Draw the list. Label every pointer.
2. Identify which standard operation this builds on.
3. Consider: do I need a dummy head? Will I need prev/curr/next?
4. Identify edge cases: empty list, single node, two nodes.

Most linked list bugs come from pointer reassignment errors. The solution is always to slow down, draw it out, and be deliberate about the order of operations.

Master these five operations and the patterns above, and you'll handle 90% of linked list interview questions with confidence.