Reverse a Linked List Using Stack
“Reverse a Linked List Using Stack” is very popular programming problem based on linked list and stack data structures. Here, we are given a linked list and our task is to reverse a linked list using stack.
Example:
Suppose, we need to reverse the following linked list: LINKED LIST: 12 -> 13 -> 14 -> 15 -> 16 After reversing the list: LINKED LIST: 16 -> 15 -> 14 -> 13 -> 12
The steps required to reverse a linked list using stack are as follows:
- If the linked list is empty, then simply return.
- Initialize a stack which can contains nodes.
- Push all the nodes in a stack except last nodes of a linked list.
- Make head to the last node of a linked list.
- Now, pop every node in stack and insert them at the end of the newly headed linked list.
- Print the reversed Linked List.
C++Program to reverse a linked list using stack is as follows:
/* C++ Program to Reverse a Linked List Using Stack */ #include<bits/stdc++.h> using namespace std; /* Strcutre of node of the Linked List */ typedef struct node { int data; struct node *next; }Node; /* Function to Insert a Node at the end of the Linked List */ void insertEnd(Node **head,int ele) { /* Creating a New Node */ Node *new_node = new Node(); new_node -> data = ele; new_node -> next = NULL; /* Check whether Linked List is empty or not */ /* If Linked List is Empty, new node will become head of the Linked List */ if(*head == NULL) { (*head) = new_node; return; } /* If Linked List is not empty, traverse the complete linked list and points the pointer of the last node of the linked list to the new node */ Node *temp = (*head); while(temp->next != NULL) temp = temp -> next; temp -> next = new_node; } /* Function to Print the Linked List */ void print(Node *head) { Node *temp = head; while(temp != NULL) { cout << temp -> data << " "; temp = temp -> next; } cout<<endl; } /* Function to Reverse a Linked List */ void reverse(Node **head) { /* Create a stack(using STL) of Node structure type */ stack<Node*>st; Node *temp = (*head); /* Insert all the nodes of the Linked List except last node */ while(temp->next != NULL) { st.push(temp); temp = temp -> next; } /* Make Last Node the new head of the linked list */ *head = temp; /* One-by-one pop all the nodes from the linked list and insert at the end of the linked list */ while(!st.empty()) { temp -> next = st.top(); temp = temp -> next; st.pop(); } temp -> next = NULL; } int main() { Node *head = NULL; /* Inserting some nodes to the Linked List */ insertEnd(&head,1); insertEnd(&head,2); insertEnd(&head,3); insertEnd(&head,4); cout<<"Linked List Before Reversing:\n"; print(head); /* Reverse a Linked List */ reverse(&head); cout<<"\nLinked List After Reversing:\n"; print(head); }
OUTPUT: Linked List Before Reversing: 1 2 3 4 Linked List After Reversing: 4 3 2 1
Related Posts:
- Reverse a Linked List.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes of the Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.
- Delete Alternate Nodes of the Linked List.
- Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
- Remove Duplicate Nodes from an Unsorted Linked List.
- Remove Duplicate Nodes from a Sorted Linked List.
- Find Union and Intersection of Two Linked List.
- Merge Two Sorted Linked List.
- Insert a New Node at the Middle of the Linked List.