Authors:
Walter Savitch ,kenrick Mock
Chapter:
Linked Data Structures
Exercise:
Programming Projects
Question:1 | ISBN:9780132846813 | Edition: 5
Question
Write a void function that takes a linked list of integers and reverses the order of its nodes. The function will have one call-by-reference parameter that is a pointer to the head of the list. After the function is called, this pointer will point to the head of a linked list that has the same nodes as the original list but in the reverse of the order they had in the original list. Note that your function will neither create nor destroy any nodes. It will simply rearrange nodes. Place your function in a suitable test program.
Answer
C++ program code:
//header section
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
};
// Function to insert a new node at the beginning of the linked list
void insert(Node*& head, int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = head;
head = newNode;
}
// Function to reverse the order of nodes in the linked list
void reverseLinkedList(Node*& head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next; // Store the next node
current->next = prev; // Reverse the link
// Move pointers one position ahead
prev = current;
current = next;
}
head = prev; // Update the head to the new first node (previously the last node)
}
// Function to print the linked list
void printLinkedList(const Node* head) {
while (head != nullptr) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
// Create a linked list
Node* head = nullptr;
insert(head, 14);
insert(head, 13);
insert(head, 12);
insert(head, 11);
// Print the original linked list
cout << "Original Linked List: ";
printLinkedList(head);
// Reverse the linked list
reverseLinkedList(head);
// Print the reversed linked list
cout << "Reversed Linked List: ";
printLinkedList(head);
return 0;
}
OUTPUT OF THE PROGRAM CODE:
Original Linked List: 11 12 13 14
Reversed Linked List: 14 13 12 11