Reversing a 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 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;

// Function to reverse the linked list
void reverse_list()
{
// Initialize current, previous and next pointers
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;
}
}

void createList(int n)
{
struct Node *newNode, *temp;
int data, i;
head = (struct Node *)malloc(sizeof(struct Node));
// When the list is empty
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
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;
{
printf("List is empty.");
}
else
{
//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();
reverse_list();
displayList();
return 0;
}

OUTPUT

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.

## 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
{
{
return;
}
}

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

{
struct node* first;
struct node* rest;

/* empty list */
return;

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 */
}

int main ()
{
printf("Linked List before reversing : ");
printf ("\n\nLinked List after reversing : ");
printf ("\n");
return 0;
}

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

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

2    3