Harshit Jindal Feb 15, 2024

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.

Recursive Algorithm

• 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() {
cout << "\n";
cout << "\n";
cout << "\n";
return 0;
}
``````

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.