A linked list is a linear data structure where each node contains two components:

• Data → stores the element value
• Pointer (next) → stores the memory address of the next node

Unlike arrays, linked lists support dynamic memory allocation, allowing them to grow or shrink during program execution. Reversing a linked list involves changing the direction of all pointers so that the last node becomes the head and the first node becomes the tail. This operation is fundamental in algorithms and applications requiring data processing in reverse order.

Algorithm to Reverse a Linked List

1. Initialize three pointers: prev = NULL, current = head, next = NULL
2. While current != NULL:
3. Store next node: next = current→next
4. Reverse pointer: current→next = prev
5. Move pointers forward: prev = current, current = next
6. Update head = prev (new first node)

Visual Example

Original List:   10 → 20 → 30 → 40 → NULL
Step-by-step reversal:

Step 1: prev=NULL, current=10, next=20
        10 → NULL   (prev=10, current=20)

Step 2: prev=10, current=20, next=30
        20 → 10 → NULL   (prev=20, current=30)

Step 3: prev=20, current=30, next=40
        30 → 20 → 10 → NULL   (prev=30, current=40)

Step 4: prev=30, current=40, next=NULL
        40 → 30 → 20 → 10 → NULL   (prev=40, current=NULL)

Final: head=40 → 30 → 20 → 10 → NULL

C Code Implementation

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

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->next = NULL;
    return newNode;
}

void insertAtEnd() {
    struct node *newNode, *temp;
    newNode = createNode();
    
    printf("Enter element to insert: ");
    scanf("%d", &newNode->data);
    
    if (head == NULL) {
        head = newNode;
    } else {
        temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    printf("Element inserted successfully!\n");
}

void reverseLinkedList() {
    struct node *prev = NULL;
    struct node *current = head;
    struct node *next = NULL;
    
    if (head == NULL) {
        printf("List is empty - nothing to reverse\n");
        return;
    }
    
    printf("Reversing linked list...\n");
    while (current != NULL) {
        next = current->next;      // Store next node
        current->next = prev;      // Reverse current node's pointer
        prev = current;            // Move prev forward
        current = next;            // Move current forward
    }
    
    head = prev;  // Update head to new first node
    printf("Linked list reversed successfully!\n");
}

void displayList() {
    struct node *temp = head;
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int menu() {
    int choice;
    printf("\n1. Insert element at end");
    printf("\n2. Reverse linked list");
    printf("\n3. Display list");
    printf("\n4. Exit");
    printf("\nEnter choice: ");
    scanf("%d", &choice);
    return choice;
}

int main() {
    printf("** Linked List Reversal Program **\n");
    while (1) {
        switch (menu()) {
            case 1: insertAtEnd(); break;
            case 2: reverseLinkedList(); break;
            case 3: displayList(); break;
            case 4: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    return 0;
}

Output

** Linked List Reversal Program **

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 1
Enter element to insert: 10
Element inserted successfully!

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 1
Enter element to insert: 20
Element inserted successfully!

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 1
Enter element to insert: 30
Element inserted successfully!

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 3
Linked List: 10 → 20 → 30 → NULL

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 2
Reversing linked list...
Linked list reversed successfully!

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 3
Linked List: 30 → 20 → 10 → NULL

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 2
Reversing linked list...
Linked list reversed successfully!

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 3
Linked List: 10 → 20 → 30 → NULL

1. Insert element at end
2. Reverse linked list
3. Display list
4. Exit
Enter choice: 4
[Program terminates]

Code Explanation

1. Node Structure Definition

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

Defines the fundamental building block of a linked list:

• data: Integer value stored in the node
• next: Pointer to the subsequent node
• head: Global pointer initialized to NULL, representing an empty list

2. Node Creation Function

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->next = NULL;
    return newNode;
}

Creates and initializes a new node with proper error handling:

• Allocates memory dynamically using malloc()
• Checks for allocation failure and exits gracefully
• Initializes next pointer to NULL
• Returns pointer to the newly created node

3. Insertion Function

void insertAtEnd() {
    struct node *newNode, *temp;
    newNode = createNode();
    
    printf("Enter element to insert: ");
    scanf("%d", &newNode->data);
    
    if (head == NULL) {
        head = newNode;
    } else {
        temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    printf("Element inserted successfully!\n");
}

Adds new nodes to the end of the list:

• If list is empty: new node becomes head
• If list has nodes: traverse to last node and append new node
• Maintains pointer connections correctly

4. Reversal Function

void reverseLinkedList() {
    struct node *prev = NULL;
    struct node *current = head;
    struct node *next = NULL;
    
    if (head == NULL) {
        printf("List is empty - nothing to reverse\n");
        return;
    }
    
    printf("Reversing linked list...\n");
    while (current != NULL) {
        next = current->next;      // Store next node
        current->next = prev;      // Reverse current node's pointer
        prev = current;            // Move prev forward
        current = next;            // Move current forward
    }
    
    head = prev;  // Update head to new first node
    printf("Linked list reversed successfully!\n");
}

Implements the classic three-pointer reversal algorithm:

• prev: Tracks the already reversed portion
• current: Points to the node being processed
• next: Temporarily stores the upcoming node
• Process continues until all nodes are reversed

5. Display Function

void displayList() {
    struct node *temp = head;
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d → ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Traverses and displays the entire list:

• Uses arrow notation (→) to visualize connections
• Clearly indicates list termination with NULL
• Handles empty list case gracefully

6. Menu Function

int menu() {
    int choice;
    printf("\n1. Insert element at end");
    printf("\n2. Reverse linked list");
    printf("\n3. Display list");
    printf("\n4. Exit");
    printf("\nEnter choice: ");
    scanf("%d", &choice);
    return choice;
}

Provides user interface with clear options for list operations.

7. Main Function

int main() {
    printf("** Linked List Reversal Program **\n");
    while (1) {
        switch (menu()) {
            case 1: insertAtEnd(); break;
            case 2: reverseLinkedList(); break;
            case 3: displayList(); break;
            case 4: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    return 0;
}

Implements interactive program loop with proper function calls based on user selection.

Alternative Reversal Methods

// Method 2: Recursive Reversal
struct node* reverseRecursive(struct node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct node* rest = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    
    return rest;
}

// Method 3: Using Stack
#include <stack.h>  // Assuming stack implementation
void reverseUsingStack() {
    if (head == NULL) return;
    
    std::stack<struct node*> nodeStack;
    struct node* temp = head;
    
    // Push all nodes to stack
    while (temp != NULL) {
        nodeStack.push(temp);
        temp = temp->next;
    }
    
    // Pop nodes and rearrange pointers
    head = nodeStack.top();
    nodeStack.pop();
    temp = head;
    
    while (!nodeStack.empty()) {
        temp->next = nodeStack.top();
        nodeStack.pop();
        temp = temp->next;
    }
    temp->next = NULL;
}

Time Complexity of Linked List Operations

Space Complexity of Linked List Operations

Practical Applications of Reversing a Linked List

// Application 1: Palindrome checking in linked list
int isPalindrome(struct node* head) {
    // Reverse the list and compare with original
    // Or use slow/fast pointer approach with stack
}

// Application 2: Reversing sub-list within larger list
struct node* reverseBetween(struct node* head, int m, int n) {
    // Reverse nodes from position m to n
}

// Application 3: Reversing in groups of k
struct node* reverseKGroup(struct node* head, int k) {
    // Reverse every k nodes in the list
}

// Application 4: Adding two numbers represented as linked lists
struct node* addTwoNumbers(struct node* l1, struct node* l2) {
    // Reverse lists, add digit by digit, reverse result
}

Common Mistakes & Solutions in Reversing a Linked List

// Mistake 1: Not storing next pointer before reversal
void incorrectReverse() {
    struct node *prev = NULL, *current = head;
    while (current != NULL) {
        current->next = prev;  // WRONG: loses reference to next node
        prev = current;
        current = current->next;  // current->next is now prev!
    }
}

// Solution: Always store next pointer first
void correctReverse() {
    struct node *prev = NULL, *current = head, *next;
    while (current != NULL) {
        next = current->next;  // CORRECT: store before changing
        current->next = prev;
        prev = current;
        current = next;
    }
}

// Mistake 2: Forgetting to update head after reversal
void reverseWithoutHeadUpdate() {
    struct node *prev = NULL, *current = head, *next;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // Missing: head = prev;
}

// Solution: Always update head pointer
head = prev;  // After loop completes

Conclusion

Linked list reversal is a fundamental algorithm with O(n) time complexity and O(1) space complexity when implemented iteratively. The three-pointer approach (prev, current, next) provides an efficient in-place reversal without requiring additional data structures. Understanding this algorithm is crucial for solving more complex problems like palindrome detection, sublist reversal, and numerical operations on linked lists.

Key Insights:

• Iterative reversal uses O(1) space, recursive uses O(n) space
• Always store the next pointer before modifying current→next
• Don’t forget to update the head pointer after reversal
• Reversal preserves node data but changes pointer direction
• The algorithm works for empty, single-node, and multi-node lists

Mastering linked list reversal provides a strong foundation for understanding pointer manipulation and algorithm design in C programming.