MCQs on Linked list with answers
- Topics >>
- Placement papers >>
- Data Structure Placement papers - Model questions & answers-02/19/15
- « Previous
- Next »
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.
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
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 data 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];
coutnext = 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#
|
/* 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
|
/* 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
"];
printList[];
moveToFront[];
document.write["
Linked List after moving last to front "];
printList[];
// This code is contributed by umadevi9616
|
Output:
Linked list before moving last to front 1 2 3 4 5 Linked list after removing last to front 5 1 2 3 4Time 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.
Article Tags :
Linked List
Practice Tags :
Linked List
Read Full Article
Program for n’th node from the end of a Linked List
Given a Linked List and a number n, write a function that returns the value at the n’th node from the end of the Linked List.
For example, if the input is below list and n = 3, then output is “B”
inserting a node at the end of a linked list
The new node will be added at the end of the linked list.