Linked lists

When to reach for it

• The input is a linked list, or a structure that pairs a list with a map, such as an LRU cache.
• You need the middle, the kth node from the end, or to detect a cycle without extra memory.
• You need to reverse all or part of a list, reorder it, or merge sorted lists.
• You must insert or delete in constant time once you hold a node.

The core idea

A singly linked list only knows each node's next node, so every operation is about not dropping a reference you still need. Before you change node.next, save what it pointed to.

Three techniques cover most questions. A dummy node in front of the head means inserting or deleting at the front works like anywhere else. Fast and slow pointers, where fast moves two steps for each step of slow, meet inside a cycle if there is one and leave slow at the middle when fast runs out. Reversal walks the list with prev, curr and a saved nxt, pointing each node back at the one before it.

A Python template

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

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next          # save the rest before rewiring
        curr.next = prev
        prev, curr = curr, nxt
    return prev                  # the new head

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                  # the second middle for even lengths

def remove_value(head, target):
    dummy = ListNode(0, head)    # the head is no longer a special case
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next   # unlink; prev stays put
        else:
            prev = prev.next
    return dummy.next

Time and space

These are single passes: O(n) time and O(1) extra space, which is the point of working with pointers instead of copying values into an array. Copying into a list first is also O(n) time but costs O(n) space; if you choose it for clarity, say so and say what it costs.

Common mistakes

• Overwriting curr.next before saving it, which cuts off the rest of the list.
• Handling the head as a special case and getting it wrong; a dummy node removes the case.
• Writing while fast.next.next without checking fast.next first, which crashes on even lengths.
• Returning the old head after reversing instead of the new one.
• Not saying what happens for an empty list or a single node.

How to explain it out loud

In a voice interview nobody can see your scratch paper, so draw the list in words: "I keep three references: prev, curr and the saved next. Each step points curr back at prev, then moves all three forward." Saying the pointer moves is how the interviewer follows you, and it is what Devana scores as thinking out loud.

After coding, trace a three-node list aloud, saying where each pointer ends. Then name the edge cases (an empty list, one node, a cycle that starts at the head) and confirm the O(1) space claim. A clear trace of pointer changes is the strongest evidence for logic explanation on these questions.