Escriba una función que mueva el último elemento al frente en una lista enlazada simple dada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la función debería cambiar la lista a 5->1->2->3->4.
Algoritmo: recorrer la lista hasta el último Node. Utilice dos punteros: uno para almacenar la dirección del último Node y otro para la dirección del penúltimo Node. Después del final del ciclo, realice las siguientes operaciones.
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
/* 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#
/* 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>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA