C Program to Reverse a Linked List

Introduction

Reversing a linked list involves changing the direction of the next pointers of the nodes so that they point to the previous node instead of the next one. This effectively reverses the order of the nodes in the list. The head of the list is updated to point to the last node, which becomes the new head after the reversal.

Example:

• Input: A linked list with nodes containing [10, 20, 30, 40].
• Output: The linked list after reversal will contain [40, 30, 20, 10].

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Reverses the linked list.
• Displays the linked list before and after the reversal.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Reverse the Linked List: Write a function that reverses the linked list by changing the next pointers of the nodes.
4. Implement the Function to Display the Linked List: Write a function to traverse and display the elements of the linked list.
5. Create a Main Function: In the main() function, create the linked list, reverse it, and display the list before and after the reversal.

C Program to Reverse a Linked List

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

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to reverse the linked list
void reverseList(struct Node** head_ref) {
    struct Node* prev = NULL;
    struct Node* current = *head_ref;
    struct Node* next = NULL;

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

    *head_ref = prev;  // Update head_ref to the new head of the reversed list
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

int main() {
    struct Node* head = NULL;

    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    // Display the linked list before reversal
    printf("Linked List before reversal: ");
    displayList(head);

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

    // Display the linked list after reversal
    printf("Linked List after reversal: ");
    displayList(head);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Reverse the Linked List

• The reverseList function takes a double pointer to the head of the linked list (head_ref).
• It uses three pointers: prev, current, and next to reverse the linked list:
  • prev starts as NULL and will eventually become the new head of the reversed list.
  • current starts as the head of the original list.
  • next temporarily stores the next node in the original list to prevent losing track of it.
• The function iterates through the list, reversing the next pointer of each node to point to the previous node (prev), effectively reversing the list.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates a linked list by inserting nodes at the end using the insertAtEnd function.
• It then displays the linked list, reverses it using the reverseList function, and displays the list again after the reversal.

Output Example

Example Output:

Linked List before reversal: 10 -> 20 -> 30 -> 40 -> NULL
Linked List after reversal: 40 -> 30 -> 20 -> 10 -> NULL

Conclusion

This C program demonstrates how to reverse a linked list. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.