Reverse a Linked List in C: In-Place 3-Pointer Algorithm

Linked list pointers change direction during list reversal.
Linked list pointers change direction during list reversal.

Problem Statement

Given the head pointer of a singly linked list with N integer nodes, reverse the linked list in-place by redirecting node pointers, and return the new head pointer.

Real-World Systems Context

In real-world systems programming, reversing singly linked lists is used in undo stacks, transaction journals, and network packet reconstruction buffers where packets arrive in reverse order.

Requirements:

  1. Construct the singly linked list using dynamic memory (malloc).
  2. Implement struct Node* reverse_list(struct Node *head) using the 3-pointer iterative technique (prev, curr, next).
  3. Print the reversed node values separated by spaces.
  4. Free all allocated heap memory cleanly with free().

Complexity & Editorial

Step-by-Step Pointer Trace

To reverse a singly linked list in-place, we must redirect each node's next pointer backwards to point to its predecessor.

Let us trace a 3-node list: [1] -> [2] -> [3] -> NULL

  • Initially: prev = NULL, curr = [1]
  • Iteration 1:
    • next = curr->next ([2])
    • curr->next = prev ([1]->NULL)
    • prev = curr ([1])
    • curr = next ([2])
  • Iteration 2:
    • next = curr->next ([3])
    • curr->next = prev ([2]->[1])
    • prev = curr ([2])
    • curr = next ([3])
  • Iteration 3:
    • next = curr->next (NULL)
    • curr->next = prev ([3]->[2])
    • prev = curr ([3])
    • curr = next (NULL)

The loop terminates when curr == NULL. We return prev, which now points to node [3], the new head of the reversed list!

Starter Code

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

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

// Reverses singly linked list in-place and returns new head
struct Node* reverse_list(struct Node *head) {
    // TODO: Implement iterative 3-pointer reversal (prev, curr, next)
    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);

    struct Node *curr = head;
    while (curr != NULL) {
        printf("%d%s", curr->data, (curr->next == NULL) ? "" : " ");
        struct Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    printf("\n");

    return 0;
}

Frequently Asked Questions

What is the time complexity of reversing a linked list?

The time complexity is strictly O(N), where N is the number of nodes in the list, because each pointer is updated exactly once.

Can a doubly linked list be reversed faster than a singly linked list?

Both take O(N) time, but in a doubly linked list you must swap both prev and next pointers on every node.

Related exercises