Dada la cabeza de una lista enlazada individualmente y un valor m , la tarea es mover los últimos m elementos al frente.
Ejemplos:
Entrada: 4->5->6->1->2->3 ; m = 3
Salida: 1->2->3->4->5->6
Entrada: 0->1->2->3->4->5 ; m = 4
Salida: 2->3->4->5->0->1
Algoritmo:
- Utilice dos punteros: uno para almacenar la dirección del último Node y otro para la dirección del primer Node.
- Recorra la lista hasta el primer Node de los últimos m Nodes.
- Mantenga dos punteros p, q, es decir, p como el primer Node de los últimos m Nodes y q justo antes del Node de p.
- Haga que el último Node sea el siguiente como el encabezado de la lista original.
- Haga que el siguiente Node q sea NULL.
- Establezca la p como la cabeza.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to move last m elements
// to front in a given linked list
#include <iostream>
using namespace std;
// A linked list node
struct Node
{
int data;
struct Node* next;
} * first, *last;
int length = 0;
// Function to print nodes
// in a given linked list
void printList(struct Node* node)
{
while (node != NULL)
{
cout << node->data <<" ";
node = node->next;
}
}
// Pointer head and p are being
// used here because, the head
// of the linked list is changed in this function.
void moveToFront(struct Node* head,
struct Node* p, int m)
{
// If the linked list is empty,
// or it contains only one node,
// then nothing needs to be done, simply return
if (head == NULL)
return;
p = head;
head = head->next;
m++;
// if m value reaches length,
// the recursion will end
if (length == m)
{
// breaking the link
p->next = NULL;
// connecting last to first &
// will make another node as head
last->next = first;
// Making the first node of
// last m nodes as root
first = head;
}
else
moveToFront(head, p, m);
}
// 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;
// making first & last nodes
if (length == 0)
last = *head_ref;
else
first = *head_ref;
// increase the length
length++;
}
// Driver code
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);
push(&start, 0);
cout << "Initial Linked list\n";
printList(start);
int m = 4; // no.of nodes to change
struct Node* temp;
moveToFront(start, temp, m);
cout << "\n Final Linked list\n";
start = first;
printList(start);
return 0;
}
// This code is contributed by SHUBHAMSINGH10
C
// C Program to move last m elements
// to front in a given linked list
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node {
int data;
struct Node* next;
} * first, *last;
int length = 0;
// Function to print nodes
// in a given linked list
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Pointer head and p are being
// used here because, the head
// of the linked list is changed in this function.
void moveToFront(struct Node* head,
struct Node* p, int m)
{
// If the linked list is empty,
// or it contains only one node,
// then nothing needs to be done, simply return
if (head == NULL)
return;
p = head;
head = head->next;
m++;
// if m value reaches length,
// the recursion will end
if (length == m) {
// breaking the link
p->next = NULL;
// connecting last to first &
// will make another node as head
last->next = first;
// Making the first node of
// last m nodes as root
first = head;
}
else
moveToFront(head, p, m);
}
// 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;
// making first & last nodes
if (length == 0)
last = *head_ref;
else
first = *head_ref;
// increase the length
length++;
}
// Driver code
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);
push(&start, 0);
printf("\n Initial Linked list\n");
printList(start);
int m = 4; // no.of nodes to change
struct Node* temp;
moveToFront(start, temp, m);
printf("\n Final Linked list\n");
start = first;
printList(start);
return 0;
}
Java
// Java Program to move last m elements
// to front in a given linked list
class GFG
{
// A linked list node
static class Node
{
int data;
Node next;
}
static Node first, last;
static int length = 0;
// Function to print nodes
// in a given linked list
static void printList(Node node)
{
while (node != null)
{
System.out.printf("%d ", node.data);
node = node.next;
}
}
// Pointer head and p are being
// used here because, the head
// of the linked list is changed in this function.
static void moveToFront(Node head, Node p, int m)
{
// If the linked list is empty,
// or it contains only one node,
// then nothing needs to be done, simply return
if (head == null)
return;
p = head;
head = head.next;
m++;
// if m value reaches length,
// the recursion will end
if (length == m)
{
// breaking the link
p.next = null;
// connecting last to first &
// will make another node as head
last.next = first;
// Making the first node of
// last m nodes as root
first = head;
}
else
moveToFront(head, p, m);
}
// UTILITY FUNCTIONS
// Function to add a node at
// the beginning of Linked List
static Node 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;
// making first & last nodes
if (length == 0)
last = head_ref;
else
first = head_ref;
// increase the length
length++;
return head_ref;
}
// Driver code
public static void main(String[] args)
{
Node start = null;
// The constructed linked list is:
// 1.2.3.4.5
start = push(start, 5);
start = push(start, 4);
start = push(start, 3);
start = push(start, 2);
start = push(start, 1);
start = push(start, 0);
System.out.printf("\n Initial Linked list\n");
printList(start);
int m = 4; // no.of nodes to change
Node temp = new Node();
moveToFront(start, temp, m);
System.out.printf("\n Final Linked list\n");
start = first;
printList(start);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program to move last m elements
# to front in a given linked list
# A linked list node
class Node :
def __init__(self):
self.data = 0
self.next = None
first = None
last = None
length = 0
# Function to print nodes
# in a given linked list
def printList( node):
while (node != None) :
print( node.data, end=" ")
node = node.next
# Pointer head and p are being
# used here because, the head
# of the linked list is changed in this function.
def moveToFront( head, p, m):
global first
global last
global length
# If the linked list is empty,
# or it contains only one node,
# then nothing needs to be done, simply return
if (head == None):
return head
p = head
head = head.next
m= m + 1
# if m value reaches length,
# the recursion will end
if (length == m) :
# breaking the link
p.next = None
# connecting last to first &
# will make another node as head
last.next = first
# Making the first node of
# last m nodes as root
first = head
else:
moveToFront(head, p, m)
# UTILITY FUNCTIONS
# Function to add a node at
# the beginning of Linked List
def push( head_ref, new_data):
global first
global last
global length
# allocate node
new_node = 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
# making first & last nodes
if (length == 0):
last = head_ref
else:
first = head_ref
# increase the length
length= length + 1
return head_ref
# Driver code
start = None
# The constructed linked list is:
# 1.2.3.4.5
start = push(start, 5)
start = push(start, 4)
start = push(start, 3)
start = push(start, 2)
start = push(start, 1)
start = push(start, 0)
print("\n Initial Linked list")
printList(start)
m = 4 # no.of nodes to change
temp = None
moveToFront(start, temp, m)
print("\n Final Linked list")
start = first
printList(start)
# This code is contributed by Arnab Kundu
C#
// C# Program to move last m elements
// to front in a given linked list
using System;
class GFG
{
// A linked list node
class Node
{
public int data;
public Node next;
}
static Node first, last;
static int length = 0;
// Function to print nodes
// in a given linked list
static void printList(Node node)
{
while (node != null)
{
Console.Write("{0} ", node.data);
node = node.next;
}
}
// Pointer head and p are being used here
// because, the head of the linked list
// is changed in this function.
static void moveToFront(Node head,
Node p, int m)
{
// If the linked list is empty,
// or it contains only one node,
// then nothing needs to be done,
// simply return
if (head == null)
return;
p = head;
head = head.next;
m++;
// if m value reaches length,
// the recursion will end
if (length == m)
{
// breaking the link
p.next = null;
// connecting last to first &
// will make another node as head
last.next = first;
// Making the first node of
// last m nodes as root
first = head;
}
else
moveToFront(head, p, m);
}
// UTILITY FUNCTIONS
// Function to add a node at
// the beginning of Linked List
static Node 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;
// making first & last nodes
if (length == 0)
last = head_ref;
else
first = head_ref;
// increase the length
length++;
return head_ref;
}
// Driver code
public static void Main(String[] args)
{
Node start = null;
// The constructed linked list is:
// 1.2.3.4.5
start = push(start, 5);
start = push(start, 4);
start = push(start, 3);
start = push(start, 2);
start = push(start, 1);
start = push(start, 0);
Console.Write("Initial Linked list\n");
printList(start);
int m = 4; // no.of nodes to change
Node temp = new Node();
moveToFront(start, temp, m);
Console.Write("\nFinal Linked list\n");
start = first;
printList(start);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript Program to move last m elements
// to front in a given linked list
// A linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
var first, last;
var length = 0;
// Function to print nodes
// in a given linked list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Pointer head and p are being used here
// because, the head of the linked list
// is changed in this function.
function moveToFront(head, p, m) {
// If the linked list is empty,
// or it contains only one node,
// then nothing needs to be done,
// simply return
if (head == null) return;
p = head;
head = head.next;
m++;
// if m value reaches length,
// the recursion will end
if (length == m) {
// breaking the link
p.next = null;
// connecting last to first &
// will make another node as head
last.next = first;
// Making the first node of
// last m nodes as root
first = head;
} else moveToFront(head, p, m);
}
// UTILITY FUNCTIONS
// Function to add a node at
// the beginning of Linked List
function push(head_ref, new_data) {
// allocate node
var 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;
// making first & last nodes
if (length == 0) last = head_ref;
else first = head_ref;
// increase the length
length++;
return head_ref;
}
// Driver code
var start = null;
// The constructed linked list is:
// 1.2.3.4.5
start = push(start, 5);
start = push(start, 4);
start = push(start, 3);
start = push(start, 2);
start = push(start, 1);
start = push(start, 0);
document.write("Initial Linked list <br>");
printList(start);
var m = 4; // no.of nodes to change
var temp = new Node();
moveToFront(start, temp, m);
document.write("<br> Final Linked list <br>");
start = first;
printList(start);
// This code is contributed by rdtank.
</script>
Producción:
Initial Linked list 0 1 2 3 4 5 Final Linked list 2 3 4 5 0 1
Complejidad temporal: O(n), donde n representa la longitud de la lista.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por Rajyalaxmi Vanam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA