Question

Given the node structure and the head pointer (headptr) of a linked list write a code to

move the last element to the head of the list.

struct node

{

   int value;

   struct node *next;

};

Answer 1

I have included my code and screenshots in this answer. In case, there is any indentation issue due to editor, then please refer to code screenshots to avoid confusion.

------------------main.cpp-----------

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

struct node //struct for node of the linked list
{
int value; // stores node value
struct node *next; // pointer to next node of linked list
};

struct node* header = NULL; //head of linked list

void insertBack(int value) //This function inserts new node at the end of the list
{
struct node* new_node = (struct node*) malloc(sizeof(struct node)); //create new node
new_node->value = value;
struct node* ptr = header;
while (ptr != NULL && ptr->next != NULL) //traverse till last element
{
ptr = ptr->next;
}
if(ptr == NULL) //if list was empty, insert first node
{
header = new_node;
new_node->next = NULL;
return;
}
ptr->next = new_node; //insert element at last position
new_node->next = NULL;
}

void LastToHead(struct node* &head) //moves the last element to the head of the list.
{
struct node* ptr = head;
while (ptr != NULL && ptr->next!= NULL && ptr->next->next != NULL) //traverse till second last element
{
ptr = ptr->next;
}
if(ptr == NULL) //if list was empty, then return
{
return;
}
if(ptr->next == NULL) //if list has only one element, then return
{
return;
}
//if list has atleast two nodes, the ptr points to second last node
ptr->next->next = head; //inserts last node into beginning of list
head = ptr->next; //makes head point to the new first node
ptr->next = NULL; //makes previous second last node as last node
}

void DisplayList(struct node* head) //This function displays the list
{
struct node* ptr = head;
cout<<"\nThe list is : ";   
while (ptr != NULL) //traverse nodes one by one and print
{
cout<< ptr->value <<" ------> ";
ptr = ptr->next;
}
cout<< "NULL" << endl;
}

int main()
{
insertBack(2); //Add elements to back of list
insertBack(4);
insertBack(6);
insertBack(14);
insertBack(61);
insertBack(22);
insertBack(16);
DisplayList(header); //display list

LastToHead(header); //inserts last node 16 to beginning of list
DisplayList(header); //display list
return 0;
}

------------------Screenshots main.cpp-----------

-/pp/linked list indented/main.cpp - Sublime Text (UNREGISTERED) ti 1) 9:07 AM * main.cpp Given the node structure and the head pointer (hea 1 #include <iostream> #include <stdlib.h> using namespace std; struct node //struct for node of the linked list 5 6 int value; // stores node value struct node *next; // pointer to next node of linked list 8 9 }; struct node* header = NULL; //head of linked list — 16 17 18 19 20 21 22 23 24 void insertBack(int value) //This function inserts new node at the end of the list { struct node* new_node = (struct node*) malloc(sizeof(struct node)); //create new node new_node->value = value; struct node* ptr = header; while (ptr != NULL && ptr->next != NULL) //traverse till last element { ptr = ptr->next; if(ptr == NULL) //if list was empty, insert first node header = new node; new_node->next = NULL; return; } ptr->next = new_node; new_node->next = NULL; //insert element at last position { 33 void LastToHead(struct node* &head) //moves the last element to the head of the list. 34 35 struct node* ptr = head; 36 while (ptr != NULL && ptr->next!= NULL && ptr->next->next != NULL) //traverse till second last element 37 38 ptr = ptr->next; 39 40 if(ptr == NULL) //if list was empty, then return 41 42 return; 43 44 if(ptr->next == NULL) //if list has only one element, then return 45 46 return; Line 13, Column 1 } Spaces: 4 C++

/cpp/linked list indented/main.cpp - Sublime Text (UNREGISTERED) ti 1) 9:07 AM * 25 26 27 28 29 30 main.cpp Given the node structure and the head pointer (hea header = new_node; new_node->next = NULL; return; } ptr->next = new node; new_node->next = NULL; //insert element at last position } void LastToHead(struct node* &head) //moves the last element to the head of the list. //traverse till second last element struct node* ptr = head; while (ptr != NULL && ptr->next!= NULL && ptr->next->next != NULL) { ptr = ptr->next; } if(ptr == NULL) //if list was empty, then return return; if(ptr->next == NULL) //if list has only one element, then return 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 { return; } //if list has atleast two nodes, the ptr points to second last node ptr->next->next = head; //inserts last node into beginning of list head = ptr->next; //makes head point to the new first node ptr->next = NULL; //makes previous second last node as last node } { 54 void DisplayList(struct node* head) //This function displays the list 55 { 56 struct node* ptr = head; 57 cout<<"\nThe list is : "; 58 while (ptr != NULL) //traverse nodes one by one and print 59 60 cout<< ptr->value <<" 61 ptr = ptr->next; 62 63 cout<< "NULL" << endl; 64 65 66 67 int main() 68 { 69 insertBack(2); //Add elements to back of list 70 insertBack 4). O Line 13, Column 1 plan Spaces: 4 C++

/cpp/linked list indented/main.cpp - Sublime Text (UNREGISTERED) ti 1) 9:07 AM * main.cpp х Given the node structure and the head pointer (hea return; } 46 47 48 49 50 51 //if list has atleast two nodes, the ptr points to second last node ptr->next->next = head; //inserts last node into beginning of list head = ptr->next; //makes head point to the new first node ptr->next = NULL; //makes previous second last node as last node } void DisplayList(struct node* head) //This function displays the list 54 55 56 struct node* ptr = head; cout<<"\nThe list is : "; while (ptr != NULL) //traverse nodes one by one and print -->"; cout<< ptr->value <<" ptr = ptr->next; cout<< "NULL" << endl; } 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 int main() { insertBack(2); // Add elements to back of list insertBack(4); insertBack(6); insertBack(14); insertBack(61); insertBack(22); insertBack(16); DisplayList(header); //display list LastToHead (header); //inserts last node 16 to beginning of list DisplayList(header); //display list return 0; } - Line 13, Column 1 Spaces: 4 C++

------------------Output-----------

9:06 AM vs@ubuntu:-/pp/linked list indented vs@ubuntu:-/pp/linked list indented$ g++ main.cpp vs@ubuntu:-/cpp/linked list indented$ ./a.out The list is : 2 ------> 4 ------> 6 ------> 14 ------> 61 ------> 22 ------> 16 ------> NULL 6 ------> 14 ------> 61 ------> 22 ------> NULL The list is : 16 ------> 2 ------> 4 vs@ubuntu:-/cpp/linked list indented$ 1

-----------------------------------------

I hope this helps you,

Please rate this answer if it helped you,

Thanks for the opportunity