C Code To Reverse A Linked List

c code to reverse a linked list is a fundamental exercise that helps programmers grasp pointer manipulation, dynamic memory management, and algorithmic thinking. Reversing a singly linked list changes the direction of the links so that the original tail becomes the new head, and every node points to its predecessor instead of its successor. Mastering this operation not only prepares you for interview questions but also builds a solid foundation for more complex data‑structure tasks such as palindrome checking, stack implementation using lists, and in‑place list modifications.

Understanding Linked Lists

A linked list is a linear collection of nodes where each node stores data and a pointer (or reference) to the next node in the sequence. In C, a typical node definition looks like this:

typedef struct Node {
    int data;               // payload
    struct Node* next;      // link to the following node
} Node;

The list itself is represented by a pointer to the first node, commonly called head. On the flip side, if head is NULL, the list is empty. Traversal follows the next pointers until a NULL sentinel is reached No workaround needed..

Why Reverse a Linked List

Reversing a linked list serves several practical purposes:

1. Algorithm preparation – Many problems (e.g., checking if a list is a palindrome) require a reversed view of the second half.
2. In‑place modification – Reversing can be done without allocating extra memory, which is crucial in memory‑constrained environments.
3. Understanding pointer dynamics – The exercise forces you to think about how pointers change direction, reinforcing concepts used in tree rotations, graph algorithms, and more.

Approaches to Reverse a Linked List in C

Two primary strategies exist: iterative and recursive. Both achieve O(n) time complexity, but they differ in space usage and conceptual clarity.

Iterative Method

The iterative approach walks through the list once, re‑assigning each node’s next pointer to point to its predecessor. Three pointers are typically employed:

• prev – holds the reversed portion’s head (initially NULL).
• current – points to the node being processed.
• next – temporarily stores the original next of current before the link is changed.

Recursive Method

The recursive solution leverages the call stack to reach the end of the list, then rewires links as the recursion unwinds. It is elegant but uses O(n) auxiliary space due to stack frames The details matter here..

Step‑by‑Step Implementation (Iterative)

Below is a complete, self‑contained C program that defines a singly linked list, builds a sample list, reverses it iteratively, and prints the result before and after reversal.

#include 
#include 

/* Node definition */
typedef struct Node {
    int data;
    struct Node* next;
} Node;

/* Utility: create a new node */
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/* Utility: push a node at the front (for easy list building) */
void pushFront(Node** headRef, int value) {
    Node* newNode = createNode(value);
    newNode->next = *headRef;
    *headRef = newNode;
}

/* Utility: print list contents */
void printList(const Node* head) {
    const Node* cur = head;
    while (cur) {
        printf("%d", cur->data);
        if (cur->next) printf(" -> ");
        cur = cur->next;
    }
    printf("\n");
}

/* Iterative reversal */
Node* reverseIterative(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;

    while (current != NULL) {
        /* Store next node */
        next = current->next;
        /* Reverse current node's pointer */
        current->next = prev;
        /* Move pointers one position ahead */
        prev = current;
        current = next;
    }
    /* prev is the new head */
    return prev;
}

/* Driver program */
int main(void) {
    Node* head = NULL;

    /* Build list: 1 -> 2 -> 3 -> 4 -> 5 */
    for (int i = 5; i >= 1; --i) {
        pushFront(&head, i);
    }

    printf("Original list: ");
    printList(head);

    head = reverseIterative(head);

    printf("Reversed list: ");
    printList(head);

    /* Free memory (optional for demo) */
    while (head) {
        Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Explanation of the iterative loop

1. next = current->next; saves the original forward link.
2. current->next = prev; flips the link to point backward.
3. prev = current; advances the prev pointer to the node just processed.
4. current = next; moves to the saved next node.
5. When current becomes NULL, all nodes have been processed, and prev points to the new head.

The algorithm touches each node exactly once, yielding O(n) time and O(1) extra space.

Step‑by‑Step Implementation (Recursive)

The recursive version is shorter but relies on the system stack. Here’s the same functionality using recursion:

Node* reverseRecursive(Node* head) {
    /* Base case: empty list or single node */
    if (head == NULL || head->next == NULL) {
        return head;
    }

    /* Recursively reverse the rest of the list */
    Node* rest = reverseRecursive(head->next);

    /* After recursion, head->next is the tail of the reversed sub‑list */
    head->next->next = head;   /* Put current node at the end */
    head->next = NULL;         /* Avoid cycle */

    return rest;               /* New head is the head of the reversed sub‑list */
}

To use it, replace the call to reverseIterative with head = reverseRecursive(head); in main. The recursive method also runs in O(n) time but consumes O(n) stack space, which may cause a stack overflow for very long lists No workaround needed..

Complexity Analysis

Conclusion

Both iterative and recursive approaches offer effective ways to reverse a linked list, each with distinct advantages depending on the context. Also, the iterative method is generally preferred for production environments due to its O(1) auxiliary space, making it suitable for large datasets where stack overflow is a concern. Its straightforward pointer manipulation ensures predictable performance and minimal memory overhead It's one of those things that adds up..

On the flip side, the recursive approach provides a more elegant and concise solution, ideal for scenarios where code brevity is prioritized and the input size is guaranteed to be small enough to avoid stack overflow. Still, its O(n) stack space usage introduces risks for very long lists, making it less dependable in memory-constrained systems.

When choosing between the two, developers should weigh the trade-offs: iterative for efficiency and safety, recursive for simplicity and readability. Understanding both methods deepens one’s grasp of linked list operations and algorithmic thinking, forming a foundation for tackling more complex data structure challenges.

By mastering these techniques, programmers gain valuable insight into optimizing code for time and space, ensuring they can adapt to varying problem constraints and requirements Still holds up..

Beyond the basic singly‑linked list reversal, the same principles can be adapted to several related scenarios, each offering its own learning opportunities Simple as that..

Doubly linked lists
When each node contains both next and prev pointers, reversal becomes a matter of swapping those two links for every node while walking the list once. The iterative version needs only a temporary pointer to hold the original next before the swap, preserving O(1) extra space and O(n) time. The recursive variant mirrors the singly‑linked case, but after the recursive call you must also fix the prev link of the returned head Surprisingly effective..

Circular linked lists
If the list forms a loop (the last node’s next points back to the head), the iterative algorithm must detect when it has returned to the starting node to avoid an infinite walk. A common technique is to keep a reference to the original head and stop the loop once current equals that reference again. The recursive version can be safeguarded by passing an additional flag that indicates whether the original head has been processed.

Tail‑recursion optimization
Some compilers can transform a tail‑recursive function into a loop, effectively giving the recursive version the same O(1) space guarantee as the iterative one. Writing the recursion so that the recursive call is the last operation—e.g., by accumulating the new head in an extra parameter—enables this optimization. That said, relying on tail‑call elimination is compiler‑specific, so portable code should still prefer the explicit iterative form when stack safety is critical Most people skip this — try not to..

In‑place reversal with a dummy node
Introducing a dummy node that points to the real head simplifies edge‑case handling (empty list or single‑node list) because the reversal loop never needs to treat the head specially. After the loop, the dummy’s next points to the new head, and the dummy can be discarded. This technique is especially useful when the reversal is part of a larger algorithm that already uses dummy nodes for merging or partitioning.

Testing and validation
A dependable test suite should cover:

• Empty list (NULL input) – returns NULL.
• Single‑node list – returns the same node unchanged.
• Two‑node list – verifies that links are correctly swapped.
• Long lists (e.g., 10⁵ nodes) – confirms O(n) runtime and that no stack overflow occurs for the iterative version.
• Circular lists – ensures the algorithm terminates and produces a properly reversed circular structure.
• Memory‑checking tools (Valgrind, AddressSanitizer) – verifies no leaks or invalid accesses.

By extending the core reversal pattern to these variants, developers reinforce their understanding of pointer manipulation, recursion limits, and the importance of tail‑call awareness. Mastery of these techniques not only prepares one for interview questions but also equips them to handle real‑world problems where linked lists appear in memory‑allocators, task schedulers, or graph traversals.

Conclusion
While the iterative method remains the safest choice for production code due to its constant auxiliary space and immunity to stack overflow, the recursive version offers a concise, expressive alternative that can be optimized by tail‑call elimination or used in educational settings to illustrate divide‑and‑conquer thinking. Adapting the reversal strategy to doubly linked, circular, or dummy‑node‑enhanced lists demonstrates the versatility of the underlying pointer‑swapping concept. At the end of the day, selecting the appropriate approach hinges on the specific constraints of the problem—balancing readability, performance, and memory safety—to produce reliable and efficient software.