C Pointer Exercises & Linked List Practice Problems

Pointer dereferencing and memory-address manipulation challenges in C.
Pointer dereferencing and memory-address manipulation challenges in C.

Problem Statement

Implement an in-place singly linked list reversal function in C using raw pointers and dynamic memory allocation with malloc().

Real-World Systems Context

Linked list reversal is the ultimate benchmark of pointer dexterity. In operating system kernels (such as the Linux kernel's list_head macro), lock-free queues, and transaction rollback logs, manipulating raw memory links without breaking pointer chains is an everyday requirement.

Task Requirements:

  1. Dynamically build a singly linked list from N input integers using malloc(sizeof(struct Node)).
  2. Implement struct Node* reverse_list(struct Node *head) in O(N) time and O(1) space using 3 pointer variables (prev, curr, next).
  3. Print the reversed list values space-separated.
  4. Free all allocated heap memory cleanly with free() to avoid memory leaks.

Complexity & Editorial

The 3-Pointer Iterative Reversal Mechanism

Reversing a singly linked list in-place requires redirecting every node's next pointer backwards toward its predecessor without losing track of the rest of the list.

If you simply execute curr->next = prev, you immediately sever the link to the remainder of the list, permanently orphaning all downstream nodes!

To prevent this, we employ the classic 3-pointer technique:

  1. Save Ahead: Save the next node in a temporary pointer: next = curr->next;
  2. Reverse Link: Redirect the current node backwards: curr->next = prev;
  3. Advance Pointers: Step both tracking pointers forward:
    prev = curr;
    curr = next;

Repeat this loop until curr == NULL. At that point, prev sits at the final node of the original list, which is now the new head of the reversed list!

Memory Hygiene: The Golden Rule of free()

When deallocating dynamic memory, never access node->next after calling free(node). Doing so is a dangerous Use-After-Free bug. Always store temp = current->next before calling free(current).

Starter Code

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

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

// Reverses singly linked list in-place
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement 3-pointer iterative reversal
    return NULL;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 1;

    struct Node *head = NULL;
    struct Node *tail = NULL;

    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
        new_node->data = val;
        new_node->next = NULL;

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    head = reverse_list(head);

    // Print list
    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%c", curr->data, curr->next == NULL ? '\n' : ' ');
        curr = curr->next;
    }

    // Free memory
    curr = head;
    while (curr != NULL) {
        struct Node *temp = curr->next;
        free(curr);
        curr = temp;
    }

    return 0;
}

Frequently Asked Questions

Why is iterative reversal preferred over recursive reversal in C?

Iterative reversal runs in O(1) space. Recursive reversal pushes a stack frame for every node, taking O(N) stack memory and risking a stack overflow crash on lists with 100,000+ nodes.

What happens if you dereference a dangling pointer after free()?

Dereferencing a freed pointer invokes Undefined Behavior (UB). The memory page may still contain stale data, or it may have been reclaimed by the heap allocator for another object, causing silent data corruption.

Related exercises