Move last element to front of a Linked-List in C++

By Manisha Rathore

In this tutorial, we will learn to move last element to front of a linked-list in C++.

For Example:

  • If the given linked list is 1->2->3->4->5
  • Then, the output is 5->1->2->3->4

Algorithm:

  • Firstly, traverse the linked list till the last node.
  • Secondly, we will use two pointers here.
  • Now, use one pointer to store the address of the last node and second pointer to store the address of the second last node.
  • Do following after the end of the loops.
  • Now make the second last node as the last node.
  • Then set next of the last node as head of the list.
  • Finally, make the last node as the head of the list.
  • The time complexity of the solution is O(s) where s is the total number of nodes in the list.

You may also like:

 

Program to move the last element to the front of a given Linked-List in C++

Hence, the implementation is here.

Code:

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

// node class
class Node 
{ 
  public: 
  int dat; 
  Node *nex; 
}; 


void mvefront(Node **head) 
{ 
  if (*head == NULL || (*head)->nex == NULL) 
    return; 

  
  Node *seclast = NULL; 
  Node *last = *head; 

  while (last->nex != NULL) 
  { 
    seclast = last; 
    last = last->nex; 
  } 

  
  seclast->nex = NULL; 


  last->nex = *head; 


  *head = last; 
} 

void push(Node** head, int newdata) 
{ 
  Node* newnode = new Node(); 


  newnode->dat = newdata; 

  newnode->nex = (*head); 

  
  (*head) = newnode; 
} 


//print
void printl(Node *node) 
{ 
  while(node != NULL) 
  { 
    cout << node->dat << " "; 
    node = node->nex; 
  } 
} 

int main() 
{ 
  Node *strt = NULL; 

  push(&strt, 5); 
  push(&strt, 4); 
  push(&strt, 3); 
  push(&strt, 2); 
  push(&strt, 1); 


  printl(strt); 
  cout<<endl;
  mvefront(&strt);  
  printl(strt); 

  return 0; 
}

OUTPUT EXPLANATION

 INPUT: 1 2 3 4 5
OUTPUT: 5 1 2 3 4

Leave a Reply