Question

In C++, Write a function to reverse the nodes in a linked list. You should not create new nodes when you reverse the the linked list.

The function prototype:          void reverse(Node*& head);

Use the following Node definition:

struct Node

{

   int data;

   Node *next;

}

Answer 1

CODE:

#include <iostream>

using namespace std;

struct node{
int value;
node *next;
};

node *reverseLinkedList(node *head){
if(head->next == NULL){
return head;
}
else{
node *ret = reverseLinkedList(head->next);
head->next->next = head;
return ret;
}
}

void add(node *&head, int val){
node *newone = new node;
newone->value = val;
newone->next = NULL;
if(head == NULL){
head = newone;
}
else{
node *temp = head;
while(temp->next != NULL){
temp = temp->next;
}
temp->next = newone;
}
}

void display(node *head){
if(head == NULL){
cout << endl;
return;
}
else{
cout << head->value << " ";
display(head->next);
}
}

int main(){
node *head = NULL;
add(head, 3);
add(head, 7);
add(head, 5);
add(head, 9);
add(head, 6);
add(head, 2);
display(head);
node *ret = reverseLinkedList(head);
head->next = NULL;
head = ret;
cout << "After reversing the list " << endl;
display(head);
return 0;
}