Linked Lists From Scratch

Linked lists in C aren’t a topic — they’re a home. C is the language where linked lists were invented as an idiom, and the study problems that use them are pure pointer manipulation, which is what C actually is. Get comfortable here and you’ve turned a topic others fear into an advantage.

The Nodes

// Singly-linked
typedef struct SNode {
    int val;
    struct SNode *next;
} SNode;

// Doubly-linked
typedef struct DNode {
    int val;
    struct DNode *prev;
    struct DNode *next;
} DNode;

LeetCode’s stock ListNode is the singly-linked variant. Get used to typing that struct without thinking.

The **head Trick (Modifying the Head In-Place)

The classic problem: “remove all nodes with value X.” If you take head by value (ListNode*), you can’t modify the caller’s head. If you take it by pointer-to-pointer (ListNode**), you can.

void remove_val(ListNode **head, int val) {
    ListNode **curr = head;
    while (*curr) {
        if ((*curr)->val == val) {
            ListNode *doomed = *curr;
            *curr = (*curr)->next;
            free(doomed);
        } else {
            curr = &(*curr)->next;
        }
    }
}

Read that slowly. curr is a pointer to the pointer we might have to change. When we delete, we update *curr (the actual link), not curr (our cursor into the list). When we advance, we set curr to the address of the current node’s next field, so the next iteration can potentially rewrite that link.

This eliminates the need for a special case for “deleting the head.” It’s the single most useful pointer trick in C, and it comes up in study problems constantly. Recognize it, then reach for it.

The Sentinel (Dummy) Node Trick

If **head feels heavy, use a sentinel: a dummy node whose next is the real head. Now you have no special case for the head because the head isn’t a special position.

ListNode *remove_val(ListNode *head, int val) {
    ListNode dummy = { .val = 0, .next = head };
    ListNode *prev = &dummy;
    while (prev->next) {
        if (prev->next->val == val) {
            ListNode *doomed = prev->next;
            prev->next = doomed->next;
            free(doomed);
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;
}

Stack-allocated sentinel — no malloc, no free needed for the sentinel itself. This is often the cleanest solution for study problems where you need to build a new list (Merge Two Sorted Lists, Add Two Numbers).

Reversal (In-Place, Iterative)

ListNode *reverse(ListNode *head) {
    ListNode *prev = NULL, *curr = head;
    while (curr) {
        ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;   // new head
}

Six lines. Memorize this. It appears verbatim inside Reverse Linked List, Reverse Between II, Reverse in K-Groups, Palindrome Linked List, and half a dozen others.

Floyd’s Cycle Detection (Tortoise and Hare)

The classic. Detect whether a linked list has a cycle in O(n) time and O(1) space.

bool has_cycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Why it works: if there’s a cycle of length k, once both pointers are inside the cycle, fast gains 1 on slow per step. They will meet within k steps. If there’s no cycle, fast reaches NULL first.

The Linked List Cycle II extension: to find where the cycle starts, once slow and fast meet inside the cycle, reset one of them to head and step both by 1. They meet at the cycle entrance. (This is a math trick from Floyd’s original paper — look it up; the derivation is a beautiful modular-arithmetic exercise.)

Finding the Middle

Same slow-and-fast setup, without the cycle check:

ListNode *middle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;   // for even length, this is the second middle
}

Merge Two Sorted Lists

ListNode *merge(ListNode *a, ListNode *b) {
    ListNode dummy = { .next = NULL };
    ListNode *tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

The sentinel + tail cursor is the cleanest possible expression of this problem. Merge K Sorted Lists is this plus a min-heap over K list heads (see 05_trees_and_heaps.md).

Doubly-Linked List: When It Pays Off

Singlys are usually enough. Reach for a doubly-linked list when:

• You need O(1) removal by node pointer (LRU Cache, LFU Cache).

• You need bidirectional traversal.

The LRU Cache problem is the classic doubly-linked list + hashmap combo. The hashmap maps key → node pointer; the list gives O(1) move-to-front. Practice this one until you can do it in 30 minutes.

Memory Discipline

LeetCode’s grader mostly doesn’t check for leaks, but you should still free the nodes you malloc. Two habits:

1. Ownership up front: when you build a list, decide if the caller frees or if a destroy_list function does it. Write the destroy function.

2. Test locally with ASan. Copy the LC boilerplate into a main, add a destroy_list, run under -fsanitize=address. Zero leaks before you submit.

When the study is over, or when M12 arrives and you’re doing systems studies, that memory discipline is what separates you from candidates who “wrote in C” but never freed anything.

What Most People Get Wrong About This

They handle the head as a special case with a branch at the top of every function (“if head == NULL return” “if head->val == target set head = head->next” …). The **head idiom and the sentinel node exist precisely to eliminate those branches. Once you’re comfortable with them, linked list code shrinks by half and becomes correct on the first try more often. That’s the compounding win.

---

Return to README.md · Next: 04_hashmaps_in_c.md