Move last element of the Linked List at first place

In the given linked list write a program to move last element to front of the linked list

Example

In this figure, we are moving last node to the front of the given linked list.

Algorithm

Time complexity: O(n)

Step 1 : create a function which takes linked list as argument and gives a new linked list with last element in front.
Step 2 : Traverse till last node.
a)    Store both last and second last node.
Step 3 : Make the second last node as last node.
a)    make the next of second last as NULL as after moving it will become the last node.
Step 4 : Make next of last as head.
Step 5 : Make the last node the head.
a)    This is done by giving changing the head pointer to last.
Step 6 : call the function on given linked list. It will print a new linked list with last as head.

C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{
struct LL* curr=new LL;

curr->data=dataToBeInserted;
curr->next=NULL;

*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

{
struct LL * last , *secondLast;

while(temp->next->next != NULL) // traverse till second last node
temp = temp->next;

secondLast = temp;
last = temp->next;

secondLast->next = NULL; //make the next of second last as NULL as after moving it will become the last node

}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head = NULL; //initial list has no elements