Dada una lista enlazada y un entero M , la tarea es agregar los últimos Nodes M de la lista enlazada al frente.
Ejemplos:
Entrada: Lista = 4 -> 5 -> 6 -> 1 -> 2 -> 3 -> NULO, M = 3
Salida: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULO
Entrada: Lista = 8 -> 7 -> 0 -> 4 -> 1 -> NULO, M = 2
Salida: 4 -> 1 -> 8 -> 7 -> 0 -> NULO
Enfoque: encuentre el primer Node de los últimos M Nodes en la lista, este Node será el nuevo Node principal, así que haga que el siguiente puntero del Node anterior sea NULL y apunte el último Node de la lista original al encabezado de la lista original . Finalmente, imprima la lista actualizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Class for a node of
// the linked list
struct Node {
// Data and the pointer
// to the next node
int data;
Node* next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
// Function to print the linked list
void printList(Node* node)
{
while (node != NULL) {
cout << (node->data) << " -> ";
node = node->next;
}
cout << "NULL";
}
// Recursive function to return the
// count of nodes in the linked list
int cntNodes(Node* node)
{
if (node == NULL)
return 0;
return (1 + cntNodes(node->next));
}
// Function to update and print
// the updated list nodes
void updateList(Node* head, int m)
{
// Total nodes in the list
int cnt = cntNodes(head);
if (cnt != m && m < cnt) {
// Count of nodes to be skipped
// from the beginning
int skip = cnt - m;
Node* prev = NULL;
Node* curr = head;
// Skip the nodes
while (skip > 0) {
prev = curr;
curr = curr->next;
skip--;
}
// Change the pointers
prev->next = NULL;
Node* tempHead = head;
head = curr;
// Find the last node
while (curr->next != NULL)
curr = curr->next;
// Connect it to the head
// of the sub list
curr->next = tempHead;
}
// Print the updated list
printList(head);
}
// Driver code
int main()
{
// Create the list
Node* head = new Node(4);
head->next = new Node(5);
head->next->next = new Node(6);
head->next->next->next = new Node(1);
head->next->next->next->next = new Node(2);
head->next->next->next->next->next = new Node(3);
int m = 3;
updateList(head, m);
return 0;
}
// This code is contributed by rutvik_56
Java
// Java implementation of the approach
class GFG {
// Class for a node of
// the linked list
static class Node {
// Data and the pointer
// to the next node
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
// Function to print the linked list
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " -> ");
node = node.next;
}
System.out.print("NULL");
}
// Recursive function to return the
// count of nodes in the linked list
static int cntNodes(Node node)
{
if (node == null)
return 0;
return (1 + cntNodes(node.next));
}
// Function to update and print
// the updated list nodes
static void updateList(Node head, int m)
{
// Total nodes in the list
int cnt = cntNodes(head);
if (cnt != m && m < cnt) {
// Count of nodes to be skipped
// from the beginning
int skip = cnt - m;
Node prev = null;
Node curr = head;
// Skip the nodes
while (skip > 0) {
prev = curr;
curr = curr.next;
skip--;
}
// Change the pointers
prev.next = null;
Node tempHead = head;
head = curr;
// Find the last node
while (curr.next != null)
curr = curr.next;
// Connect it to the head
// of the sub list
curr.next = tempHead;
}
// Print the updated list
printList(head);
}
// Driver code
public static void main(String[] args)
{
// Create the list
Node head = new Node(4);
head.next = new Node(5);
head.next.next = new Node(6);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(2);
head.next.next.next.next.next = new Node(3);
int m = 3;
updateList(head, m);
}
}
Python3
# Python3 implementation of the approach
# Class for a node of
# the linked list
class newNode:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
# Function to print the linked list
def printList(node):
while (node != None):
print(node.data, "->", end=" ")
node = node.next
print("NULL")
# Recursive function to return the
# count of nodes in the linked list
def cntNodes(node):
if (node == None):
return 0
return (1 + cntNodes(node.next))
# Function to update and print
# the updated list nodes
def updateList(head, m):
# Total nodes in the list
cnt = cntNodes(head)
if (cnt != m and m < cnt):
# Count of nodes to be skipped
# from the beginning
skip = cnt - m
prev = None
curr = head
# Skip the nodes
while (skip > 0):
prev = curr
curr = curr.next
skip -= 1
# Change the pointers
prev.next = None
tempHead = head
head = curr
# Find the last node
while (curr.next != None):
curr = curr.next
# Connect it to the head
# of the sub list
curr.next = tempHead
# Print the updated list
printList(head)
# Driver code
# Create the list
head = newNode(4)
head.next = newNode(5)
head.next.next = newNode(6)
head.next.next.next = newNode(1)
head.next.next.next.next = newNode(2)
head.next.next.next.next.next = newNode(3)
m = 3
updateList(head, m)
# This code is contributed by shubhamsingh10
C#
// C# implementation of the approach
using System;
class GFG {
// Class for a node of
// the linked list
class Node {
// Data and the pointer
// to the next node
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
// Function to print the linked list
static void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " -> ");
node = node.next;
}
Console.Write("NULL");
}
// Recursive function to return the
// count of nodes in the linked list
static int cntNodes(Node node)
{
if (node == null)
return 0;
return (1 + cntNodes(node.next));
}
// Function to update and print
// the updated list nodes
static void updateList(Node head, int m)
{
// Total nodes in the list
int cnt = cntNodes(head);
if (cnt != m && m < cnt) {
// Count of nodes to be skipped
// from the beginning
int skip = cnt - m;
Node prev = null;
Node curr = head;
// Skip the nodes
while (skip > 0) {
prev = curr;
curr = curr.next;
skip--;
}
// Change the pointers
prev.next = null;
Node tempHead = head;
head = curr;
// Find the last node
while (curr.next != null)
curr = curr.next;
// Connect it to the head
// of the sub list
curr.next = tempHead;
}
// Print the updated list
printList(head);
}
// Driver code
public static void Main(String[] args)
{
// Create the list
Node head = new Node(4);
head.next = new Node(5);
head.next.next = new Node(6);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(2);
head.next.next.next.next.next = new Node(3);
int m = 3;
updateList(head, m);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
// Class for a node of
// the linked list
class Node {
// Data and the pointer
// to the next node
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to print the linked list
function printList(node) {
while (node != null) {
document.write(node.data + " -> ");
node = node.next;
}
document.write("NULL");
}
// Recursive function to return the
// count of nodes in the linked list
function cntNodes(node) {
if (node == null) return 0;
return 1 + cntNodes(node.next);
}
// Function to update and print
// the updated list nodes
function updateList(head, m) {
// Total nodes in the list
var cnt = cntNodes(head);
if (cnt != m && m < cnt) {
// Count of nodes to be skipped
// from the beginning
var skip = cnt - m;
var prev = null;
var curr = head;
// Skip the nodes
while (skip > 0) {
prev = curr;
curr = curr.next;
skip--;
}
// Change the pointers
prev.next = null;
var tempHead = head;
head = curr;
// Find the last node
while (curr.next != null) curr = curr.next;
// Connect it to the head
// of the sub list
curr.next = tempHead;
}
// Print the updated list
printList(head);
}
// Driver code
// Create the list
var head = new Node(4);
head.next = new Node(5);
head.next.next = new Node(6);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(2);
head.next.next.next.next.next = new Node(3);
var m = 3;
updateList(head, m);
// This code is contributed by rdtank.
</script>
Producción
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
MÉTODO 2:
Usaremos la modificación de la técnica del corredor: –
1. encuentre el k-ésimo Node desde el final usando la técnica del corredor y realice las siguientes modificaciones
2. ahora tenemos que actualizar nuestros punteros como
a) fast->next estará apuntando a la cabeza,
b)lento->el siguiente será un nuevo jefe,
c) el último Node será el lento->siguiente, por lo tanto, debería apuntar a nulo
C++
#include <iostream>
using namespace std;
struct node {
int data;
node* next;
node(int x)
{
data = x;
next = NULL;
}
};
void insertAtTail(node*& head, int x)
{
if (head == NULL) {
head = new node(x);
return;
}
node* curr = head;
while (curr->next != NULL) {
curr = curr->next;
}
node* t = new node(x);
curr->next = t;
}
void print(node* head)
{
node* curr = head;
while (curr != NULL) {
cout << curr->data << " -> ";
curr = curr->next;
}
cout << "NULL\n";
}
node* appendK(node* head, int k)
{
node* fast = head;
node* slow = head;
for (int i = 0; i < k; i++) {
fast = fast->next;
}
while (fast->next != NULL) {
slow = slow->next;
fast = fast->next;
}
// cout<<"data"<<" "<<slow->data<<" "<<fast->data<<endl;
fast->next = head;
head = slow->next;
slow->next = NULL;
return head;
}
int main()
{
node* head = NULL;
int n;
n = 6 ;
insertAtTail(head, 4);
insertAtTail(head, 5);
insertAtTail(head, 6);
insertAtTail(head, 1);
insertAtTail(head, 2);
insertAtTail(head, 3);
int k;
k = 3 ;
head = appendK(head, k % n);
print(head);
return 0;
}
Java
// Java code to the above approach
import java.io.*;
class GFG {
class Node {
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
}
public Node insertAtTail(Node head, int x)
{
if (head == null) {
head = new Node(x);
return head;
}
Node curr = head;
while (curr.next != null) {
curr = curr.next;
}
Node t = new Node(x);
curr.next = t;
return head;
}
public void print(Node head)
{
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " -> ");
curr = curr.next;
}
System.out.print("NULL\n");
}
public Node appendK(Node head, int k)
{
Node fast = head;
Node slow = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
fast.next = head;
head = slow.next;
slow.next = null;
return head;
}
public static void main(String[] args)
{
GFG l = new GFG();
Node head = null;
int n = 6;
head = l.insertAtTail(head, 4);
head = l.insertAtTail(head, 5);
head = l.insertAtTail(head, 6);
head = l.insertAtTail(head, 1);
head = l.insertAtTail(head, 2);
head = l.insertAtTail(head, 3);
int k = 3;
head = l.appendK(head, k % n);
l.print(head);
}
}
// This code is contributed by lokesh (lokeshmvs21).
Producción
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Publicación traducida automáticamente
Artículo escrito por mishrakishan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA