Imprime los últimos k Nodes de la lista enlazada en orden inverso | Enfoque recursivo

Dada una lista enlazada que contiene N Nodes y un número entero positivo k debe ser menor o igual que N. La tarea es imprimir los últimos k Nodes de la lista en orden inverso.
Ejemplos: 
 

Input: list: 1->2->3->4->5, k = 2                       
Output: 5 4

Input: list: 3->10->6->9->12->2->8, k = 4 
Output: 8 2 12 9

Fuente: Amazon Interview Experience SDE Off Campus .
 

Enfoque recursivo: recorrer recursivamente la lista enlazada. Al regresar de cada llamada recursiva, mantenga un registro del número de Node, considerando el último Node como el número 1, el penúltimo como el número 2 y así sucesivamente. Este conteo podría rastrearse con la ayuda de una variable global o de puntero. Con la ayuda de esta variable de recuento, imprima los Nodes que tengan un número de Node menor o igual que k .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to print the last k nodes
// of linked list in reverse order
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node
struct Node {
    int data;
    Node* next;
};
 
// Function to get a new node
Node* getNode(int data)
{
    // allocate space
    Node* newNode = new Node;
 
    // put in data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// Function to print the last k nodes
// of linked list in reverse order
void printLastKRev(Node* head,
                     int& count, int k)
{
    // if list is empty
    if (!head)
        return;
 
    // Recursive call with the next node
    // of the list
    printLastKRev(head->next, count, k);
 
    // Count variable to keep track of
    // the last k nodes
    count++;
 
    // Print data
    if (count <= k)
        cout << head->data << " ";
}
 
// Driver code
int main()
{
    // Create list: 1->2->3->4->5
    Node* head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(3);
    head->next->next->next = getNode(4);
    head->next->next->next->next = getNode(5);
 
    int k = 4, count = 0;
 
    // print the last k nodes
    printLastKRev(head, count, k);
 
    return 0;
}

// Java implementation to print the last k nodes
// of linked list in reverse order
class GfG
{
 
// Structure of a node
static class Node
{
    int data;
    Node next;
}
 
// Function to get a new node
static Node getNode(int data)
{
    // allocate space
    Node newNode = new Node();
 
    // put in data
    newNode.data = data;
    newNode.next = null;
    return newNode;
}
 
static class C
{
    int count = 0;
}
 
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, C c, int k)
{
    // if list is empty
    if (head == null)
        return;
 
    // Recursive call with the next node
    // of the list
    printLastKRev(head.next, c, k);
 
    // Count variable to keep track of
    // the last k nodes
    c.count++;
 
    // Print data
    if (c.count <= k)
        System.out.print(head.data + " ");
}
 
// Driver code
public static void main(String[] args)
{
    // Create list: 1->2->3->4->5
    Node head = getNode(1);
    head.next = getNode(2);
    head.next.next = getNode(3);
    head.next.next.next = getNode(4);
    head.next.next.next.next = getNode(5);
 
    int k = 4;
    C c = new C();
 
    // print the last k nodes
    printLastKRev(head, c, k);
}
}
  
// This code is contributed by prerna saini

# Python implementation to print the last k nodes
# of linked list in reverse order
 
# Node class
class Node:
     
    # Function to initialise the node object
    def __init__(self, data):
        self.data = data # Assign data
        self.next =None
 
# Function to get a new node
def getNode(data):
 
    # allocate space
    newNode = Node(0)
 
    # put in data
    newNode.data = data
    newNode.next = None
    return newNode
 
class C:
    def __init__(self, data):
        self.count = data
 
# Function to print the last k nodes
# of linked list in reverse order
def printLastKRev(head, c, k):
 
    # if list is empty
    if (head == None):
        return
 
    # Recursive call with the next node
    # of the list
    printLastKRev(head.next, c, k)
 
    # Count variable to keep track of
    # the last k nodes
    c.count = c.count + 1
 
    # Print data
    if (c.count <= k) :
        print(head.data, end = " ")
 
# Driver code
 
# Create list: 1->2->3->4->5
head = getNode(1)
head.next = getNode(2)
head.next.next = getNode(3)
head.next.next.next = getNode(4)
head.next.next.next.next = getNode(5)
 
k = 4
c = C(0)
 
# print the last k nodes
printLastKRev(head, c, k)
 
# This code is contributed by Arnab Kundu

// C# implementation to print the last k 
// nodes of linked list in reverse order
using System;
 
class GFG
{
 
// Structure of a node
public class Node
{
    public int data;
    public Node next;
}
 
// Function to get a new node
static Node getNode(int data)
{
    // allocate space
    Node newNode = new Node();
 
    // put in data
    newNode.data = data;
    newNode.next = null;
    return newNode;
}
 
public class C
{
    public int count = 0;
}
 
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, C c, int k)
{
    // if list is empty
    if (head == null)
        return;
 
    // Recursive call with the next
    // node of the list
    printLastKRev(head.next, c, k);
 
    // Count variable to keep track 
    // of the last k nodes
    c.count++;
 
    // Print data
    if (c.count <= k)
        Console.Write(head.data + " ");
}
 
// Driver code
public static void Main(String []args)
{
     
    // Create list: 1->2->3->4->5
    Node head = getNode(1);
    head.next = getNode(2);
    head.next.next = getNode(3);
    head.next.next.next = getNode(4);
    head.next.next.next.next = getNode(5);
 
    int k = 4;
    C c = new C();
 
    // print the last k nodes
    printLastKRev(head, c, k);
}
}
 
// This code is contributed by Arnab Kundu

<script>
 
// Javascript implementation of the approach
 
// Structure of a node
class Node {
        constructor() {
                this.data = 0;
                this.next = null;
             }
        }
         
         
// Function to get a new node
function getNode( data)
{
    // allocate space
    var newNode = new Node();
 
    // put in data
    newNode.data = data;
    newNode.next = null;
    return newNode;
}
 
 class C
{
constructor() {
    this.count = 0;
    }
}
 
// Function to print the last k nodes
// of linked list in reverse order
function printLastKRev( head,  c,  k)
{
    // if list is empty
    if (head == null)
        return;
 
    // Recursive call with the next node
    // of the list
    printLastKRev(head.next, c, k);
 
    // Count variable to keep track of
    // the last k nodes
    c.count++;
 
    // Print data
    if (c.count <= k)
        document.write(head.data + " ");
}
 
// Driver Code
 
// Create list: 1->2->3->4->5
var head = getNode(1);
head.next = getNode(2);
head.next.next = getNode(3);
head.next.next.next = getNode(4);
head.next.next.next.next = getNode(5);
 
let k = 4;
let c = new C();
 
// print the last k nodes
printLastKRev(head, c, k);
 
// This code is contributed by jana_sayantan.
</script>

5 4 3 2

Complejidad temporal: O(n).
Enfoque iterativo: la idea es utilizar la estructura de datos de pila . 
 

1. Empuje todos los Nodes de la lista vinculada a una pila.
2. Saque los Nodes k de la pila e imprímalos.

Complejidad temporal: O(n).
Enfoque de dos punteros La idea es similar a encontrar el k-ésimo Node desde el final de la lista enlazada . 
 

1. Mover el primer puntero k Nodes adelante.
2. Ahora comience otro puntero, el segundo desde la cabeza.
3. Cuando el primer puntero llega al final, el segundo apunta al k-ésimo Node.
4. Finalmente, usando el segundo puntero, imprima los últimos k Nodes.

Complejidad temporal: O(n).