Site icon Study Algorithms

Reverse a singly Linked List.

Question: How will you reverse a singly Linked List?

Input:– 4 -> 8 -> 15 -> 16 -> 23 -> 42

Output:– 42 -> 23 -> 16 -> 15 -> 8 -> 4

Reversing a singly Linked List is based upon a very simple concept. We just need to swap the “NEXT” value of each of the node, as we iterate over the list.

That means that after the complete process, the first node should point to NULL, and the second last node should point to the first node…and so on.

Initial Condition:-
8 -> NEXT is 15
15 -> NEXT is 16

After “1” iteration

16 -> NEXT is 15
15 -> NEXT is 8

After the entire process is complete, we set the last node as the HEAD and assign NULL to the first node.
Here is an implementation of the same in C.

#include<stdio.h>

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

//function to reverse a single Linked List
struct node * reverseList(struct node * head)
{
    // we will use these 2 variables to swap the pointers of next nodes
    struct node * temp = NULL;
    struct node * nextNode = NULL;

    // loop to reverse the list
    while(head)
    {
        // storing the pointer of the next node
        nextNode = head -> next;

        // swap started
        // changing the NEXT pointer of 1st node
        head -> next = temp;

        // storing the address to continue the swap in next iteration
        temp = head;

        head = nextNode;
    }

    // after the loop is complete, temp points at the last node
    // or we can say, the first node of the reversed list
    // we return this value.
    return temp;
}

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

struct node * addElement(struct node *head, int number)
{
    struct node * temp = (struct node*)malloc(sizeof(struct node));
    temp -> data = number;
    temp -> next = NULL;
    struct node * temp2 = head;
    while(temp2 -> next != NULL)
        temp2 = temp2 -> next;
    temp2 -> next = temp;
    return head;
}

int main(void)
{
    //creating a list
    struct node * listHead = (struct node*)malloc(sizeof(struct node));
    listHead->data = 4;
    listHead->next = NULL;
    listHead = addElement(listHead, 8);
    listHead = addElement(listHead, 15);
    listHead = addElement(listHead, 16);
    listHead = addElement(listHead, 23);
    listHead = addElement(listHead, 42);

    printList(listHead);  // Initial list

    listHead = reverseList(listHead);

    printList(listHead);  // Reversed list

    return 0;
}

4, 8, 15, 16, 23, 42

42, 23, 16, 15, 8, 4

Exit mobile version