Program to Reverse a Singly Linked List in C

This program demonstrates how to reverse a singly linked list in C. The reversal is achieved by iteratively changing the direction of the pointers in the list.

Program Structure

The program consists of the following components:

• struct Node: Defines the structure of a node in the singly linked list.
• insert function: Adds a new node to the front of the list.
• printList function: Prints the elements of the list.
• reverseList function: Reverses the singly linked list.
• main function: Demonstrates the use of these functions.

Program Code

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

// Definition of the singly linked list node structure
struct Node {
    int data;          // Data stored in the node
    struct Node* next; // Pointer to the next node
};

// Function to insert a new node at the front of the list
void insert(struct Node** head_ref, int new_data) {
    // Allocate memory for the new node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    // Assign data to the new node
    new_node->data = new_data;
    // Link the new node to the current head
    new_node->next = *head_ref;
    // Update the head to point to the new node
    *head_ref = new_node;
}

// Function to print the linked list
void printList(struct Node* node) {
    // Traverse the list and print each node's data
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// Function to reverse the linked list
void reverseList(struct Node** head_ref) {
    struct Node* prev = NULL;  // Initialize previous node to NULL
    struct Node* current = *head_ref;  // Start with the head node
    struct Node* next = NULL;  // Initialize next node to NULL
    
    // Traverse the list and reverse the links
    while (current != NULL) {
        next = current->next;  // Store the next node
        current->next = prev;  // Reverse the current node's pointer
        prev = current;  // Move the previous pointer forward
        current = next;  // Move the current pointer forward
    }
    // Update the head to the last node, which is now the first node
    *head_ref = prev;
}

// Main function to demonstrate the reversal
int main() {
    struct Node* head = NULL;

    // Insert elements into the list
    insert(&head, 5);
    insert(&head, 10);
    insert(&head, 15);
    insert(&head, 20);

    // Print the original list
    printf("Original List: \n");
    printList(head);

    // Reverse the linked list
    reverseList(&head);

    // Print the reversed list
    printf("Reversed List: \n");
    printList(head);

    return 0;
}
    

Explanation

The program starts by defining a Node structure, which consists of an integer data field and a pointer to the next node. The insert function is used to add new nodes at the beginning of the list, updating the head pointer accordingly.

The printList function traverses the linked list from the head to the end, printing each node’s data. The reverseList function is where the reversal logic takes place. It iterates through the list, adjusting the pointers to reverse the direction of the list. Finally, the main function demonstrates the process by creating a list, printing it, reversing it, and then printing the reversed list.

Output

When the program is run, the output will be:

Original List: 
20 -> 15 -> 10 -> 5 -> NULL
Reversed List: 
5 -> 10 -> 15 -> 20 -> NULL