# Linked List Reversal

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

Reversing Text From a File in Pytho...
Reversing Text From a File in Python (Video 42)
• A data item.
• An address of the next node.
``````class Node
{
int data;
Node *next;
};
`````` This article will introduce how to reverse a linked list given the pointer to the head node of the linked list.

## Linked List Reversal Algorithm

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.

## Linked List Reversal Illustration ## Linked List Reversal Implementation

``````#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* curr = head;
Node *prev = NULL, *next = NULL;

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

{
if (head == NULL || head->next == NULL)

Node* rest = recursiveReverse(head->next);
return rest;
}

{

stack<Node*> s;
Node* temp = *head;
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()
{
Node* head = new Node(1);
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);
printList(head); cout << "\n";
printList(head); cout << "\n";
printList(head); cout << "\n";
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.

## Related Article - Data Structure

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Linked List

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion