Question

Write a program void reverse_list(list **l)in pseudo-code or C++ to reverse the direction of a given singly-linked list. In other words, after the reversal all pointers should now point backwards. Your algorithm should take linear time. The node of this singly-linked list is defined as

typedef struct list {

item_type item;

struct list ∗ next ; }

list;

void reverse_list(list **l){








}

Remark: 15 points for completely correct. 10 points for correctly reversing the list with minor errors.

Answer 1

PROGRAM IN C++:

#include<iostream>
#include<malloc.h>
using namespace std;

typedef struct list{ //node definition of linked list
int item;
struct list *next;}
list;

void reverse_list(list **l){ //function to reverse nodes of linked list
list *temp = NULL;
list *prev = NULL;
list *current = (*l);
while(current != NULL) {
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
(*l) = prev;
}

void printnodes(list *head) { //function to print the nodes of linked list
while(head != NULL) {
cout<<head->item<<" ";
head = head->next;
}
}

void push(list **l, int item) { //function to add nodes in linked list
list *node;
node = (list *)malloc(sizeof(list));
node->item = item;
node->next = (*l);
(*l) = node;
}

int main() { // The main driver function
list *head = NULL;
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "Original linked list" << endl;
printnodes(head);
reverse_list(&head);
cout << endl;
cout << "Reversed linked list"<<endl;
printnodes(head);
return 0;
}

output: