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.
a)ย ย ย  last->next = *head makes the last node’s next 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.

Algorithm working Example

C++ Program

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

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==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
			*head=curr;
		}
		
		//O(1) constant time
}

void moveLastNode(struct LL **head) 
{
	struct LL *temp = *head;
	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
	last->next = *head; //make the last node's next as head
	
	*head = last; //make the last node the head
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	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
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"The list initially is :-\n";
	display(&head);
	
	moveLastNode(&head);
	cout<<"\nAfter moving last node to front the list becomes :-\n";
	display(&head);
	
	return 0;
}

Translate ยป