Comprehensive Guide to Singly Linked List Implementation and Common Interview Problems in C

Linked lists are a fundamental data structure used in many systems such as the Linux kernel, Redis, and Python. This article focuses on singly linked lists (including some circular list cases) and provides a complete C implementation.

Definition

typedef struct ListNode {
    struct ListNode *next;
    int value;
} ListNode;

Basic operations include creating a node, inserting at head or tail, deleting a node, traversing, creating a list from an array, and computing length. The implementations are shown below.

ListNode *listNewNode(int value) {
    ListNode *node;
    if (!(node = malloc(sizeof(ListNode))))
        return NULL;
    node->value = value;
    node->next = NULL;
    return node;
}

ListNode *listAddNodeHead(ListNode *head, int value) {
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;
    if (head)
        node->next = head;
    head = node;
    return head;
}

ListNode *listAddNodeTail(ListNode *head, int value) {
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;
    return listAddNodeTailWithNode(head, node);
}

ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node) {
    if (!head) {
        head = node;
    } else {
        ListNode *current = head;
        while (current->next) {
            current = current->next;
        }
        current->next = node;
    }
    return head;
}

ListNode *listDelNode(ListNode *head, int value) {
    ListNode *current = head, *prev = NULL;
    while (current) {
        if (current->value == value) {
            if (current == head)
                head = head->next;
            if (prev)
                prev->next = current->next;
            free(current);
            break;
        }
        prev = current;
        current = current->next;
    }
    return head;
}

void listTraverse(ListNode *head) {
    ListNode *current = head;
    while (current) {
        printf("%d", current->value);
        printf("->");
        current = current->next;
        if (current == head) // handle circular list
            break;
    }
    printf("NULL\n");
}

ListNode *listCreate(int a[], int len) {
    ListNode *head = NULL;
    for (int i = 0; i < len; i++) {
        if (!(head = listAddNodeTail(head, a[i])))
            return NULL;
    }
    return head;
}

int listLength(ListNode *head) {
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

Interview problems covered:

Reverse a list (iterative and recursive).

Copy a list (iterative and recursive).

Merge two sorted lists (iterative and recursive).

Detect intersection of two lists.

Detect a loop (Floyd’s algorithm) and find the loop entry.

Add two numbers represented by linked lists.

Insert a node into a sorted (non‑circular and circular) list.

Find the k‑th node from the end (two‑pass and one‑pass).

Each problem is accompanied by concise C code, for example the iterative reverse:

ListNode *listReverse(ListNode *head) {
    ListNode *newHead = NULL, *current = head;
    while (current) {
        ListNode *next = current->next;
        current->next = newHead;
        newHead = current;
        current = next;
    }
    return newHead;
}

Additional explanations describe algorithmic ideas such as using two‑pointer techniques for loop detection and k‑th‑from‑end retrieval, as well as handling edge cases for circular sorted lists.