In which linked list the last node points to the first?

Move last element to front of a given Linked List

Write a function that moves the last element to the front in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 5->1->2->3->4.

Table of Contents Show

Move last element to front of a given Linked List
What is the last node of linked list points to the first node the list called?

Algorithm:
Traverse the list till last node. Use two pointers: one to store the address of last node and other for address of second last node. After the end of loop do following operations.
i) Make second last as last (secLast->next = NULL).
ii) Set next of last as head (last->next = *head_ref).
iii) Make last as head ( *head_ref = last)

C++

/* CPP Program to move last element 
to front in a given linked list */
#include <bits/stdc++.h>

using namespace std;
/* A linked list node */

class Node
{ 

public:

int data;

Node *next;
}; 
/* We are using a double pointer
head_ref here because we change 
head of the linked list inside 
this function.*/

void moveToFront(Node **head_ref)
{ 

/* If linked list is empty, or

it contains only one node,

then nothing needs to be done,

simply return */

if (*head_ref == NULL || (*head_ref)->next == NULL)

return;

/* Initialize second last

and last pointers */

Node *secLast = NULL;

Node *last = *head_ref;

/*After this loop secLast contains

address of second last node and

last contains address of last node in Linked List */

while (last->next != NULL)

{

secLast = last;

last = last->next;

}

/* Set the next of second last as NULL */

secLast->next = NULL;

/* Set next of last as head node */

last->next = *head_ref;

/* Change the head pointer

to point to last node now */

*head_ref = last;
} 
/* UTILITY FUNCTIONS */
/* Function to add a node 
at the beginning of Linked List */

void push(Node** head_ref, int new_data)
{ 

/* allocate node */

Node* new_node = new Node();

/* put in the data */

new_node->data = new_data;

/* link the old list off the new node */

new_node->next = (*head_ref);

/* move the head to point to the new node */

(*head_ref) = new_node;
} 
/* Function to print nodes in a given linked list */

void printList(Node *node)
{ 

while(node != NULL)

{

cout << node->data << " ";

node = node->next;

}
} 
/* Driver code */

int main()
{ 

Node *start = NULL;

/* The constructed linked list is:

1->2->3->4->5 */

push(&start, 5);

push(&start, 4);

push(&start, 3);

push(&start, 2);

push(&start, 1);

cout<<"Linked list before moving last to front\n";

printList(start);

moveToFront(&start);

cout<<"\nLinked list after removing last to front\n";

printList(start);

return 0;
} 
// This code is contributed by rathbhupendra

/* C Program to move last element to front in a given linked list */
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */

struct Node
{

int data;

struct Node *next;
};
/* We are using a double pointer head_ref here because we change

head of the linked list inside this function.*/

void moveToFront(struct Node **head_ref)
{

/* If linked list is empty, or it contains only one node,

then nothing needs to be done, simply return */

if (*head_ref == NULL || (*head_ref)->next == NULL)

return;

/* Initialize second last and last pointers */

struct Node *secLast = NULL;

struct Node *last = *head_ref;

/*After this loop secLast contains address of second last

node and last contains address of last node in Linked List */

while (last->next != NULL)

{

secLast = last;

last = last->next;

}

/* Set the next of second last as NULL */

secLast->next = NULL;

/* Set next of last as head node */

last->next = *head_ref;

/* Change the head pointer to point to last node now */

*head_ref = last;
}
/* UTILITY FUNCTIONS */
/* Function to add a node at the beginning of Linked List */

void push(struct Node** head_ref, int new_data)
{

/* allocate node */

struct Node* new_node =

(struct Node*) malloc(sizeof(struct Node));

/* put in the data */

new_node->data = new_data;

/* link the old list off the new node */

new_node->next = (*head_ref);

/* move the head to point to the new node */

(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */

void printList(struct Node *node)
{

while(node != NULL)

{

printf("%d ", node->data);

node = node->next;

}
}
/* Driver program to test above function */

int main()
{

struct Node *start = NULL;

/* The constructed linked list is:

1->2->3->4->5 */

push(&start, 5);

push(&start, 4);

push(&start, 3);

push(&start, 2);

push(&start, 1);

printf("\n Linked list before moving last to front\n");

printList(start);

moveToFront(&start);

printf("\n Linked list after removing last to front\n");

printList(start);

return 0;
}

Java

/* Java Program to move last element to front in a given linked list */

class LinkedList
{

Node head; // head of list

/* Linked list Node*/

class Node

{

int data;

Node next;

Node(int d) {data = d; next = null; }

}

void moveToFront()

{

/* If linked list is empty or it contains only

one node then simply return. */

if(head == null || head.next == null)

return;

/* Initialize second last and last pointers */

Node secLast = null;

Node last = head;

/* After this loop secLast contains address of

second last node and last contains address of

last node in Linked List */

while (last.next != null)

{

secLast = last;

last = last.next;

}

/* Set the next of second last as null */

secLast.next = null;

/* Set the next of last as head */

last.next = head;

/* Change head to point to last node. */

head = last;

}

/* Utility functions */

/* Inserts a new Node at front of the list. */

public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/* Function to print linked list */

void printList()

{

Node temp = head;

while(temp != null)

{

System.out.print(temp.data+" ");

temp = temp.next;

}

System.out.println();

}

/* Driver program to test above functions */

public static void main(String args[])

{

LinkedList llist = new LinkedList();

/* Constructed Linked List is 1->2->3->4->5->null */

llist.push(5);

llist.push(4);

llist.push(3);

llist.push(2);

llist.push(1);

System.out.println("Linked List before moving last to front ");

llist.printList();

llist.moveToFront();

System.out.println("Linked List after moving last to front ");

llist.printList();

}
} 
/* This code is contributed by Rajat Mishra */

Python3

# Python3 code to move the last item to front

class Node:

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

# Function to add a node

# at the beginning of Linked List

def push(self, data):

new_node = Node(data)

new_node.next = self.head

self.head = new_node

# Function to print nodes in a

# given linked list

def printList(self):

tmp = self.head

while tmp is not None:

print(tmp.data, end=", ")

tmp = tmp.next

print()

# Function to bring the last node to the front

def moveToFront(self):

tmp = self.head

sec_last = None # To maintain the track of

# the second last node

# To check whether we have not received

# the empty list or list with a single node

if not tmp or not tmp.next:

return

# Iterate till the end to get

# the last and second last node

while tmp and tmp.next :

sec_last = tmp

tmp = tmp.next

# point the next of the second

# last node to None

sec_last.next = None

# Make the last node as the first Node

tmp.next = self.head

self.head = tmp
# Driver Code

if __name__ == '__main__':

llist = LinkedList()

# swap the 2 nodes

llist.push(5)

llist.push(4)

llist.push(3)

llist.push(2)

llist.push(1)

print ("Linked List before moving last to front ")

llist.printList()

llist.moveToFront()

print ("Linked List after moving last to front ")

llist.printList()

/* C# Program to move last element to front in a given linked list */

using System;

class LinkedList
{ 

Node head; // head of list

/* Linked list Node*/

public class Node

{

public int data;

public Node next;

public Node(int d) {data = d; next = null; }

}

void moveToFront()

{

/* If linked list is empty or it contains only

one node then simply return. */

if(head == null || head.next == null)

return;

/* Initialize second last and last pointers */

Node secLast = null;

Node last = head;

/* After this loop secLast contains address of

second last node and last contains address of

last node in Linked List */

while (last.next != null)

{

secLast = last;

last = last.next;

}

/* Set the next of second last as null */

secLast.next = null;

/* Set the next of last as head */

last.next = head;

/* Change head to point to last node. */

head = last;

}

/* Utility functions */

/* Inserts a new Node at front of the list. */

public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/* Function to print linked list */

void printList()

{

Node temp = head;

while(temp != null)

{

Console.Write(temp.data+" ");

temp = temp.next;

}

Console.WriteLine();

}

/* Driver program to test above functions */

public static void Main(String []args)

{

LinkedList llist = new LinkedList();

/* Constructed Linked List is 1->2->3->4->5->null */

llist.push(5);

llist.push(4);

llist.push(3);

llist.push(2);

llist.push(1);

Console.WriteLine("Linked List before moving last to front ");

llist.printList();

llist.moveToFront();

Console.WriteLine("Linked List after moving last to front ");

llist.printList();

}
} 
// This code is contributed by Arnab Kundu

Javascript

<script>
/* javascript Program to move last element to front in a given linked list */

/* Linked list Node */

class Node {

constructor(val) {

this.data = val;

this.next = null;

}

}

var head; // head of list

function moveToFront() {

/*

* If linked list is empty or it contains only one node then simply return.

*/

if (head == null || head.next == null)

return;

/* Initialize second last and last pointers */

var secLast = null;

var last = head;

/*

* After this loop secLast contains address of second last node and last

* contains address of last node in Linked List

*/

while (last.next != null) {

secLast = last;

last = last.next;

}

/* Set the next of second last as null */

secLast.next = null;

/* Set the next of last as head */

last.next = head;

/* Change head to point to last node. */

head = last;

}

/* Utility functions */

/* Inserts a new Node at front of the list. */

function push(new_data) {

/*

* 1 & 2: Allocate the Node & Put in the data

*/

var new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/* Function to print linked list */

function printList() {

var temp = head;

while (temp != null) {

document.write(temp.data + " ");

temp = temp.next;

}

document.write();

}

/* Driver program to test above functions */

/* Constructed Linked List is 1->2->3->4->5->null */

push(5);

push(4);

push(3);

push(2);

push(1);

document.write("Linked List before moving last to front<br/> ");

printList();

moveToFront();

document.write("<br/>Linked List after moving last to front <br/>");

printList();
// This code is contributed by umadevi9616 
</script>

Output:

Linked list before moving last to front 1 2 3 4 5 Linked list after removing last to front 5 1 2 3 4

Time Complexity: O(n) where n is the number of nodes in the given Linked List.

?list=PLqM7alHXFySH41ZxzrPNj2pAYPOI8ITe7
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.