Singly Link List Reversal

Like the way we have implemented singly link list traversal meaning that we have printed the link list in the order they were inserted we will print them in reverse order.

The working of this code is as follows:-

---

Code for Doubly Link List with proper explanation is as follows: -

Declaring a Node-

• Here we are creating Node where we will enter the data.

• It consists of 2 components like the way we do traversal of singly link list:

  • Data.

  • Address of next Node.

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

Inserting a node in link list-

In this section of code, we are creating a newNode where data of newNode will be created and stored.

// Function to insert a new node at the beginning of the linked list
void insert(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for a new node
    if (new_node == NULL) {     // Check if memory allocation was successful
        printf("Memory allocation failed!\n");
        return; // Exit the function if memory allocation failed
    }    
    new_node->data = new_data;  // Set the data of the new node to the value provided by the user
    new_node->next = *head_ref; // Make the next of the new node point to the current head of the list
    *head_ref = new_node;// Move the head pointer to point to the new node, making it the new head of the list
}

---

Reverse the link list before printing

In this section we are reversing the link list.

void reverse(struct Node** head_ref) {
    struct Node* prev = NULL; // Initialize the previous node to NULL
    struct Node* current = *head_ref; // Start with the head of the list
    struct Node* next = NULL; // Initialize the next node pointer to NULL
    while (current != NULL) {
        next = current->next; // Store the next node (to move forward)
        current->next = prev; // Reverse the link: point current node to the previous node
        prev = current;       // Move prev pointer one step forward to current node
        current = next;      // Move to the next node in the original list
    }    
    *head_ref = prev; // After the loop, update the head_ref to point to the new head (prev)
}

---

Printing the link list-

In this section we are printing the link list.

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) { //traverse the whole link list
        printf("%d -> ", node->data); //printing the data
        node = node->next; //moving the node forward after printing 
    }
    printf("NULL\n");
}

---

Main function

Here we are printing the main function for the code.

int main() {
    struct Node* head = NULL;
    int n, value;
    // Input the number of nodes
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    // Input values for each node
    for (int i = 0; i < n; i++) {
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &value);
        insert(&head, value);
    }    
    printf("Original linked list: ");
    printList(head); 
    // Reverse the linked list
    reverse(&head);
    printf("Reversed linked list: ");
    printList(head);    
    return 0;
}

---

Complete code

The complete code of printing the link list in reverse order.

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

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

void insert(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

void reverse(struct Node** head_ref) {
    struct Node* prev = NULL;
    struct Node* current = *head_ref;
    struct Node* next = NULL;

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

    *head_ref = prev;
}

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

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

    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &value);
        insert(&head, value);
    }

    printf("Original linked list: ");
    printList(head);

    reverse(&head);

    printf("Reversed linked list: ");
    printList(head);

    return 0;
}

Example of the code-

---