Home » Interview Questions » LinkedList Interview Questions » Move last element of the Linked List at first place

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;
}

READ  Detect a loop in the Linked List

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions