C program to reverse a Singly Linked List

Write a C program to create a singly linked list of n nodes and reverse the order of nodes of the given linked list. How to reverse a singly linked list in C.

Reversing singly linked list in C

Required knowledge

Basic C programming, Singly Linked List, Dynamic memory allocation

Algorithm to reverse a Singly Linked List

Algorithm to reverse a Singly Linked List
%%Input : head node of the linked list
Begin:
    If (head != NULL) then
        prevNodehead
        headhead.next
        curNodehead
        prevNode.nextNULL
        While (head != NULL) do
            headhead.next
            curNode.nextprevNode
            prevNodecurNode
            curNodehead
        End while
        headprevNode
    End if
End


Steps to reverse a Singly Linked List

Create two more pointers other than head namely prevNode and curNode that will hold the reference of previous node and current node respectively.
Make sure that prevNode points to first node i.e. prevNode = head.
head should now point to its next node i.e. the second node head = head->next.
curNode should also points to the second node i.e. curNode = head.
Reversing linked list in C
Now, disconnect the previous node i.e. the first node from others. We will make sure that it points to none. As this node is going to be our last node. Perform operation prevNode->next = NULL.
Reversing linked list in C
Move the head node to its next node i.e. head = head->next.
Reversing linked list in C
Now, re-connect the current node to its previous node i.e. curNode->next = prevNode;.
Reversing linked list in C
Point the previous node to current node and current node to head node. Means they should now point to prevNode = curNode; and curNode = head.
Reversing linked list in C
Repeat steps 3-5 till head pointer becomes NULL.
Reversing linked list in C

Reversing linked list in C

Reversing linked list in C

Reversing linked list in C
Now, after all nodes has been re-connected in the reverse order. Make the last node as the first node. Means the head pointer should point to prevNode pointer. Perform head = prevNode;. And finally you end up with a reversed linked list of its original.
Reversing linked list in C


Program to revere a Singly Linked List

/**
 * C program to reverse a Singly Linked List
 */

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


/* Structure of a node */
struct node {
    int data; //Data part
    struct node *next; //Address part
}*head;



void createList(int n);
void reverseList();
void displayList();



int main()
{
    int n, choice;

    /*
     * Creates a singly linked list of n nodes
     */
    printf("Enter the total number of nodes: ");
    scanf("%d", &n);
    createList(n);

    printf("\nData in the list \n");
    displayList();

    /*
     * Reverses the list
     */
    printf("\nPress 1 to reverse the order of singly linked list\n");
    scanf("%d", &choice);
    if(choice == 1)
    {
        reverseList();
    }

    printf("\nData in the list\n");
    displayList();

    return 0;
}



/*
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = (struct node *)malloc(sizeof(struct node));

    /*
     * If unable to allocate memory for head node
     */
    if(head == NULL)
    {
        printf("Unable to allocate memory.");
    }
    else
    {
        /*
         * Reads data of node from the user
         */
        printf("Enter the data of node 1: ");
        scanf("%d", &data);

        head->data = data; //Links the data field with data
        head->next = NULL; //Links the address field to NULL

        temp = head;

        /*
         * Creates n nodes and adds to linked list
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            /* If memory is not allocated for newNode */
            if(newNode == NULL)
            {
                printf("Unable to allocate memory.");
                break;
            }
            else
            {
                printf("Enter the data of node %d: ", i);
                scanf("%d", &data);

                newNode->data = data; //Links the data field of newNode with data
                newNode->next = NULL; //Links the address field of newNode with NULL

                temp->next = newNode; //Links previous node i.e. temp to the newNode
                temp = temp->next;
            }
        }

        printf("SINGLY LINKED LIST CREATED SUCCESSFULLY\n");
    }
}



/*
 * Reverse the order of nodes of a singly linked list
 */
void reverseList()
{
    struct node *prevNode, *curNode;

    if(head != NULL)
    {
        prevNode = head;
        curNode = head->next;
        head = head->next;

        prevNode->next = NULL; //Makes the first node as last node

        while(head != NULL)
        {
            head = head->next;
            curNode->next = prevNode;

            prevNode = curNode;
            curNode = head;
        }

        head = prevNode; //Makes the last node as head

        printf("SUCCESSFULLY REVERSED LIST\n");
    }
}



/*
 * Displays the entire list
 */
void displayList()
{
    struct node *temp;

    /*
     * If the list is empty i.e. head = NULL
     */
    if(head == NULL)
    {
        printf("List is empty.");
    }
    else
    {
        temp = head;
        while(temp != NULL)
        {
            printf("Data = %d\n", temp->data); //Prints the data of current node
            temp = temp->next; //Advances the position of current node
        }
    }
} 

Output
Enter the total number of nodes: 5
Enter the data of node 1: 10
Enter the data of node 2: 20
Enter the data of node 3: 30
Enter the data of node 4: 40
Enter the data of node 5: 50
SINGLY LINKED LIST CREATED SUCCESSFULLY

Data in the list
Data = 10
Data = 20
Data = 30
Data = 40
Data = 50

Press 1 to reverse the order of singly linked list
1
SUCCESSFULLY REVERSED LIST

Data in the list
Data = 50
Data = 40
Data = 30
Data = 20
Data = 10

Happy coding ;)


Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment