Timed Linked-List Manipulation in C: Edge-Case Handling

Welcome back. Last time, you used compiler warnings and AddressSanitizer to distinguish an invalid access from a leak or a use-after-free. A linked-list interview problem brings those concerns together: the pointer changes may produce the right visible values while still losing a node, freeing the wrong one, or leaving the caller with a stale head pointer.

Today you’ll solve one manipulation problem in C under a 24-minute timer, then review the pointer reasoning and verify your implementation on your Linux VM. Allow about 45–50 minutes overall. The goal is not just a passing example: it is a solution whose edge cases, ownership, and complexity you can explain aloud.

The problem and its ownership contract

Remove the $n$th node from the end of a singly linked list. Return the resulting head. For example, removing the second node from the end of the list containing 1, 2, 3, 4, 5 leaves 1, 2, 3, 5.

Use these interview assumptions:

• The input is a well-formed, acyclic singly linked list. Each node was allocated separately with malloc, and the caller owns the list.
• If $1\le n\le$ the list length, remove exactly one node and free it. Allocate no replacement nodes.
• If the list is empty, $n\le 0$, or $n$ exceeds the length, leave the list unchanged.
• Return the head in every case. The caller must use that return value because removing the original head changes it.

That last point is a C ownership issue, not merely an interface detail. After a head removal, the caller’s old head value refers to freed storage. The safe call is head = remove_nth_from_end(head, n);; the caller must not subsequently use an alias to the removed node.

A two-pass solution—measure the length, then find the predecessor—is a reasonable starting explanation. For this attempt, aim for one traversal toward the tail after an initial pointer separation, $O(n)$ time, and $O(1)$ extra space. Decide how you will find the node before the one to remove: in a singly linked list, that is the node whose link you must change.

Your 24-minute interview run

Save the following as list.c. The function deliberately does nothing yet; replace its body. The test harness builds fresh heap-allocated lists, checks the returned sequence, and releases the remaining nodes. Leave the harness unchanged during your first attempt.

#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int value;
    struct Node *next;
};

static void free_list(struct Node *head)
{
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

static struct Node *build(const int *values, size_t count)
{
    struct Node *head = NULL;
    struct Node **link = &head;

    for (size_t i = 0; i < count; ++i) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) {
            free_list(head);
            perror("malloc");
            exit(EXIT_FAILURE);
        }
        node->value = values[i];
        node->next = NULL;
        *link = node;
        link = &node->next;
    }
    return head;
}

static struct Node *remove_nth_from_end(struct Node *head, int n)
{
    /* Replace this placeholder with your implementation. */
    (void)n;
    return head;
}

static void check(const char *label,
                  const int *input, size_t input_count, int n,
                  const int *expected, size_t expected_count)
{
    struct Node *head = build(input, input_count);
    head = remove_nth_from_end(head, n);

    struct Node *current = head;
    for (size_t i = 0; i < expected_count; ++i) {
        assert(current != NULL);
        assert(current->value == expected[i]);
        current = current->next;
    }
    assert(current == NULL);

    free_list(head);
    printf("passed: %s\n", label);
}

#define LEN(a) (sizeof(a) / sizeof((a)[0]))

int main(void)
{
    const int five[] = {1, 2, 3, 4, 5};
    const int middle[] = {1, 2, 3, 5};
    const int tail[] = {1, 2, 3, 4};
    const int new_head[] = {2, 3, 4, 5};
    const int one[] = {7};
    const int two[] = {7, 8};
    const int second[] = {8};
    const int repeated[] = {2, 2, 2};
    const int repeated_result[] = {2, 2};

    check("middle", five, LEN(five), 2, middle, LEN(middle));
    check("tail", five, LEN(five), 1, tail, LEN(tail));
    check("head", five, LEN(five), 5, new_head, LEN(new_head));
    check("single node", one, LEN(one), 1, NULL, 0);
    check("two nodes", two, LEN(two), 2, second, LEN(second));
    check("empty", NULL, 0, 1, NULL, 0);
    check("zero n", five, LEN(five), 0, five, LEN(five));
    check("n too large", five, LEN(five), 6, five, LEN(five));
    check("repeated values", repeated, LEN(repeated), 2,
          repeated_result, LEN(repeated_result));
    return 0;
}

Set your timer. Spend roughly three minutes stating the contract and boundary cases, four minutes choosing your pointer arrangement, twelve minutes coding, and five minutes compiling, testing, and explaining. Before changing any next field, ask: Which pointer still gives me access to the node or remainder I need? The repeated-values case is also a reminder that the task is to remove a node, not merely to make one example’s values look right.

Build and run with the same instrumentation mindset as the previous lesson:

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
  -fno-omit-frame-pointer -fsanitize=address \
  list.c -o list

ASAN_OPTIONS=detect_leaks=1 ./list

Clang can replace GCC in that command. An assertion failure means a result is wrong; a sanitizer report may reveal an invalid access or a removed node that was never freed. If a case fails, inspect that case before changing the algorithm wholesale. Stop here until your timer ends, even if some cases remain failing.

Review the pointer strategy

Now watch the relevant parts of Remove nth node from end of Linked List (LeetCode 19) by Nikhil Lohia. Its problem statement assumes $n$ is valid; our C contract additionally specifies what to do for invalid values and requires releasing the removed heap allocation.

The useful invariant is a fixed gap between two pointers. Place a stack-allocated dummy node before the head, with its next field set to head. Start both pointers at the dummy and advance the leading pointer $n$ links. If it cannot advance that far, $n$ is too large and the list stays unchanged. Otherwise, move both pointers together until the leading pointer reaches the tail. The trailing pointer then sits immediately before the node to remove.

Why start at the dummy rather than at head? When $n$ equals the list length, the target is the head. In that case the trailing pointer must be able to remain before the head. The dummy provides a real next field to update, yet it consumes only constant stack space and is never returned.

Reference implementation and verification

Compare your function with this implementation only after your timed run:

static struct Node *remove_nth_from_end(struct Node *head, int n)
{
    if (n <= 0)
        return head;

    struct Node dummy = { .value = 0, .next = head };
    struct Node *fast = &dummy;
    struct Node *slow = &dummy;

    for (int i = 0; i < n; ++i) {
        if (fast->next == NULL)
            return head;             /* n exceeds the list length */
        fast = fast->next;
    }

    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    struct Node *victim = slow->next;
    slow->next = victim->next;        /* Bypass while victim is valid. */
    free(victim);                     /* Release exactly the removed node. */
    return dummy.next;
}

The for loop never dereferences a null pointer: it checks fast->next before advancing. After $n$ successful advances, fast is $n$ links ahead of slow. Their simultaneous movement preserves that gap. At the end, fast is at the tail, so slow->next is the $n$th node from the end. Valid $n$ guarantees victim is not null.

Notice the order of the final operations. victim->next is read before free(victim); after the release, even inspecting victim->next would be a use-after-free. The dummy remains a local stack object, so the function returns dummy.next, not &dummy. It frees no surviving nodes. The function uses $O(n)$ time in the worst case and $O(1)$ extra space.

Run the instrumented build again after any correction. Passing all assertions checks the requested sequences and boundaries; a clean sanitizer run adds evidence that the tested paths do not leak the removed node or access it after release. Neither replaces the ownership argument: for example, a caller that retained another pointer to victim would still have a dangling alias after this function returns.

Key takeaways

In a timed linked-list problem, make the contract explicit before coding: valid range, empty input, head and tail changes, and who frees a removed node. A dummy node gives the head a predecessor; a fixed gap lets two pointers locate the target’s predecessor without a length-counting pass. In C, finish the reasoning at the memory boundary: reconnect the survivors while the removed node is valid, free it once, and return the possibly changed head.

The next lesson shifts from pointer rewiring to timed bit manipulation, where the same interview habit applies: justify each operation, state its edge cases, and verify the C behavior rather than relying on a familiar-looking expression.