Reversing a Linked List | Operation on Linked List

10 min read

Reversing a Linked List means reversing the elements of the given Linked List. In this case, let us assume that you are given the pointer to the head node of a linked list. You need to now change the next pointer of every node so that the order of the entire Linked List is reversed. 

Reversing a linked list

Reversing a singly linked list (Iterative approach)

  • Initialize pointers prev as NULL, curr as head and next as NULL.
  • Iterate through the list. In a loop, do the following.

               /*  Before changing next pointer of current node,
                store the next node  */
               next = curr -> next
               /*   Change next pointer of current node  */
               /*  Actual reversing  */
               curr -> next = prev
               /*   Move prev and curr one step ahead  */
               prev = curr
               curr = next

 

Iterative C program to reverse a singly linked list

// Iterative C program to reverse a linked list
#include<stdio.h>
#include<stdlib.h>
void createList(int n);
void reverse_list();
void displayList();

//Creating node with data and a pointer
struct Node {
int data;
struct Node *next;
}*head;

// Function to reverse the linked list
void reverse_list()
{
// Initialize current, previous and next pointers
Node *current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL)
{
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead
prev = current;
current = next;
}
head = prev;
}

void createList(int n)
{
struct Node *newNode, *temp;
int data, i;
head = (struct Node *)malloc(sizeof(struct Node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct Node *)malloc(sizeof(struct Node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}}}}

void displayList()
{
struct Node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
//Print the list
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}}


int main()
{
int n;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nThe Reversed Linked List is\n");
reverse_list();
displayList();
return 0;
}

 

OUTPUT

reverse a linked list

 

Time Complexity: O(n)
Space Complexity: O(1)

 

Reversing a singly linked list (Recursive approach)

1) Break the linked list into two parts - first node and rest of the linked list.

2) Call reverse function for rest of the linked list.

3) Link rest and first.

4) Change the head pointer.

 

Recursive C program to reverse a singly linked list

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

//Creating node with data and a pointer
struct node
{
int data;
struct node *next;
};

//Print the list
void print_list(struct node *head)
{
if (head == NULL)
{
return;
}
printf("%d ", head -> data);
print_list(head -> next);
}


void insert_node (struct node ** head, int new_data)
{
struct node * new_node = (struct node *) malloc (sizeof (struct node));
new_node -> data = new_data;
new_node -> next = *head;
*head= new_node;
}

void recursive_reverse(struct node** head)
{
struct node* first;
struct node* rest;

/* empty list */
if (*head == NULL)
return;

first = *head;
rest = first->next;

/* List has only one node */
if (rest == NULL)
return;

/* reverse the rest list and put the first element at the last */
recursive_reverse(&rest);
first->next->next = first;

first->next = NULL;

/* change the head pointer */
*head = rest;
}

int main ()
{
struct node *head = NULL;
insert_node(&head, 5);
insert_node(&head, 4);
insert_node(&head, 3);
insert_node(&head, 2);
insert_node(&head, 1);
printf("Linked List before reversing : ");
print_list(head);
printf ("\n\nLinked List after reversing : ");
recursive_reverse(&head);
print_list(head);
printf ("\n");
return 0;
}

Time Complexity: O(n)
Space Complexity: O(1)
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error