C Program to Reverse a Singly Linked List

1. Introduction

A singly linked list is a data structure that consists of nodes. Each node contains a data element and a pointer to the next node. The process of reversing a singly linked list involves changing the direction of the 'next' pointers so that the first node points to NULL and the last node points to what was originally the first node.

2. Program Overview

In this program, we will:

1. Define the basic structure of a node in a singly linked list.

2. Implement functions to:

- Create a new node.

- Insert an element at the beginning of the list.

- Display the linked list.

- Reverse the singly linked list.

3. Code Program

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

// Define the node structure for a singly linked list
struct Node {
    int data;             // Data part of the node
    struct Node* next;    // Pointer to the next node
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert an element at the beginning of the singly linked list
void insertBegin(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

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

// Function to reverse the singly linked list
void reverseList(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

int main() {
    struct Node* head = NULL;
    insertBegin(&head, 50);
    insertBegin(&head, 40);
    insertBegin(&head, 30);
    insertBegin(&head, 20);
    insertBegin(&head, 10);
    displayList(head);
    reverseList(&head);
    printf("Reversed ");
    displayList(head);
    return 0;
}

Output:

Linked List: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Reversed Linked List: 50 -> 40 -> 30 -> 20 -> 10 -> NULL

4. Step By Step Explanation

1. We define the structure of a node for the singly linked list using the struct keyword. Each Node contains an integer data and a pointer to the next node.

2. The createNode function creates a new node with the provided data.

3. The insertBegin function inserts a new node at the beginning of the list.

4. The displayList function is used to display the linked list.

5. The reverseList function is the key function that reverses the linked list. It works by maintaining three pointers: prev, current, and next. These pointers traverse the list and reverse the direction of the 'next' pointers.

6. In the main function, we demonstrate the insertion of elements, displaying the list, and reversing it.