Harshit Jindal Dec 26, 2022 Feb 26, 2021

A linked list is a linear data structure. A node of the linked list consists of:

• A data item.
• An address of the next node.
``````class Node
{
int data;
Node *next;
};
`````` Let the `head` be the first node of the linked list.

### Iterative Algorithm

• ##### Traverse the linked list until you reach the last node i.e. `curr` != `NULL` and do the following:
• Set `next` as `curr->next` to move `next` to its next node.
• Reverse current node’s direction by pointing them toward `prev`. So, set `curr->next` as `prev`
• Set `prev` as `curr` to move it one position ahead.
• Set `curr` as `next` to move it one position ahead.

### Reverse Linked List Using Stack

• ##### Update the next pointer of the last node to `NULL`. • ##### Move `prev` to `curr` i.e. node with data as `8` and `curr` to `NULL` and the algorithm terminates.

``````#include <bits/stdc++.h>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};

{
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
}

{

Node *prev = NULL, *next = NULL;

while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}

{

return rest;
}

{

stack<Node*> s;
while (temp->next != NULL)
{
s.push(temp);
temp = temp->next;
}

while (!s.empty())
{
temp->next = s.top();
s.pop();
temp = temp->next;
}
temp->next = NULL;
}

int main()
{
head -> next = new Node(2);
head -> next-> next = new Node(3);
head -> next-> next-> next = new Node(4);
head -> next-> next-> next-> next = new Node(5);
head -> next-> next-> next-> next-> next = new Node(6);
return 0;
}
``````

## Linked List Reversal Algorithm Complexity

### Time Complexity

• Average Case

To reverse the complete linked list, we have to visit every node and then append it to reversed list. So, if a linked list has `n` nodes, the average-case time complexity of traversal is of the order of `O(n)`. The time complexity is of the order of `O(n)`.

• Best Case

The best-case time complexity is `O(n)`. It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is `O(n)`. It is the same as best-case time complexity.

### Space Complexity

This traversal algorithm’s space complexity is `O(1)` as no extra space other than for temporary pointers is required.

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.