Reverse a linked list | Board Infinity

Introduction

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The objective is to reverse a linked list given a pointer to the head node. By altering the connections between the nodes, the list must be reversed.

How to reverse a linked list iteratively

Curr, Prev, and Next are three pointers that are supposed to be used to maintain track of nodes and update reverse linkages.

Algorithm

Initialize three pointers prev as NULL, curr as head, and next as NULL.

Iterate through the linked list. In a loop, do the following:

Before changing the next of curr, store the next node

next = curr -> next

Now update the next pointer of curr to the prev

curr -> next = prev

Update prev as curr and curr as next

prev = curr

curr = next

Example

C program for reversing the linked list.

#include <stdio.h>

#include <stdlib.h>

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Function to reverse the linked list */

static void reverse(struct Node** head)

{

struct Node* prev = NULL;

struct Node* current = *head;

struct Node* next = NULL;

while (current != NULL) {

next = current->next;

// Reverse current node's pointer

current->next = prev;

// Move pointers one position ahead.

prev = current;

current = next;

}

*head = prev;

}

/* Function to push a node */

void push(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;

}

/* Function to print linked list */

void printList(struct Node* head)

{

struct Node* temp = head;

while (temp != NULL) {

printf("%d ", temp->data);

temp = temp->next;

}

int main()

{

struct Node* head = NULL;

push(&head, 89); //add elements to linkedlist

push(&head, 3);

push(&head, 45);

push(&head, 23);

printf("Linked list\n");

printList(head);

reverse(&head);

printf("\nReversed linked list \n");

printList(head);

getchar();

}

Output

Linked list
23 45 3 89
Reversed linked list
89 3 45 23

Time Complexity: O(N), Traversing over the linked list of size N.

Auxiliary Space: O(1)

Reverse a linked list using recursion

The goal is to use recursion to get to the linked list's last node before beginning the reverse operation.

Algorithm

The initial node and the remainder of the linked list should be separated into two parts.
For the rest of the linked list, call reverse.
Add a link to the first in the linked list.
Make the head pointer NULL.

Example:

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

/* Link list node */
struct Node {
int data;
struct Node* next;
};

/* Function to reverse the linked list */
static struct Node* reverse(struct Node* head)
{

if (head == NULL || head->next == NULL)
return head;

/* reverse the rest list and put
the first element at the end */
struct Node* rest = reverse(head->next);
head->next->next = head;

head->next = NULL;

/* fix the head pointer */
return head;
}

/* Function to push a node */
struct Node * push(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;
}

/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}

int main()
{

struct Node* head = NULL;

head=push(head, 89); //add elements to linkedlist
head=push(head, 3);
head=push(head, 45);
head=push(head, 23);

printf("Linked list\n");
printList(head);
head=reverse(head);
printf("\nReversed linked list \n");
printList(head);
getchar();
}

write your code here: Coding Playground

Output:

Linked list
23 45 3 89
Reversed linked list
89 3 45 23

Time Complexity: O(N), Visiting over every node one time

Auxiliary Space: O(N), Function call stack space