Dada una lista enlazada que contiene N Nodes y un entero positivo K donde 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
La solución discutida en la publicación anterior utiliza un enfoque recursivo. El siguiente artículo analiza tres enfoques iterativos para resolver el problema anterior.
Enfoque 1: la idea es utilizar una estructura de datos de pila. Empuje todos los valores de datos de los Nodes de la lista vinculada para apilar y abrir los primeros elementos K e imprimirlos.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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 k)
{
// if list is empty
if (!head)
return;
// Stack to store data value of nodes.
stack<int> st;
// Push data value of nodes to stack
while (head) {
st.push(head->data);
head = head->next;
}
int cnt = 0;
// Pop first k elements of stack and
// print them.
while (cnt < k) {
cout << st.top() << " ";
st.pop();
cnt++;
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
return 0;
}
Java
// Java implementation to print the last k nodes
// of linked list in reverse order
import java.util.*;
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Stack to store data value of nodes.
Stack<Integer> st = new Stack<Integer>();
// Push data value of nodes to stack
while (head != null)
{
st.push(head.data);
head = head.next;
}
int cnt = 0;
// Pop first k elements of stack and
// print them.
while (cnt < k)
{
System.out.print(st.peek() + " ");
st.pop();
cnt++;
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to print the last k nodes
# of linked list in reverse order
import sys
import math
# Structure of a node
class Node:
def __init__(self,data):
self.data = data
self.next = None
# Function to get a new node
def getNode(data):
# allocate space and return new node
return Node(data)
# Function to print the last k nodes
# of linked list in reverse order
def printLastKRev(head,k):
# if list is empty
if not head:
return
# Stack to store data value of nodes.
stack = []
# Push data value of nodes to stack
while(head):
stack.append(head.data)
head = head.next
cnt = 0
# Pop first k elements of stack and
# print them.
while(cnt < k):
print("{} ".format(stack[-1]),end="")
stack.pop()
cnt += 1
# Driver code
if __name__=='__main__':
# 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
# print the last k nodes
printLastKRev(head,k)
# This Code is Contributed by Vikash Kumar 37
C#
// C# implementation to print the last k nodes
// of linked list in reverse order
using System;
using System.Collections.Generic;
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Stack to store data value of nodes.
Stack<int> st = new Stack<int>();
// Push data value of nodes to stack
while (head != null)
{
st.Push(head.data);
head = head.next;
}
int cnt = 0;
// Pop first k elements of stack and
// print them.
while (cnt < k)
{
Console.Write(st.Peek() + " ");
st.Pop();
cnt++;
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to print the last k nodes
// of linked list in reverse order
// Structure of a node
class Node {
constructor(val) {
this.data = val;
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;
}
// Function to print the last k nodes
// of linked list in reverse order
function printLastKRev(head , k) {
// if list is empty
if (head == null)
return;
// Stack to store data value of nodes.
var st = [];
// Push data value of nodes to stack
while (head != null) {
st.push(head.data);
head = head.next;
}
var cnt = 0;
// Pop first k elements of stack and
// print them.
while (cnt < k) {
document.write(st.pop() + " ");
cnt++;
}
}
// 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);
var k = 4;
// print the last k nodes
printLastKRev(head, k);
// This code contributed by aashish1995
</script>
Producción:
5 4 3 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
El espacio auxiliar del enfoque anterior se puede reducir a O(k) . La idea es usar dos punteros. Coloque el primer puntero al principio de la lista y mueva el segundo puntero al principio del formulario del k-ésimo Node. Luego busque el k-ésimo Node desde el final usando el enfoque discutido en este artículo: Buscar el k-ésimo Node desde el final de la lista enlazada . Después de encontrar el k-ésimo Node desde el final, empuje todos los Nodes restantes en la pila. Saque todos los elementos uno por uno de la pila e imprímalos.
A continuación se muestra la implementación del enfoque eficiente anterior:
C++
// 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 k)
{
// if list is empty
if (!head)
return;
// Stack to store data value of nodes.
stack<int> st;
// Declare two pointers.
Node *first = head, *sec = head;
int cnt = 0;
// Move second pointer to kth node.
while (cnt < k) {
sec = sec->next;
cnt++;
}
// Move first pointer to kth node from end
while (sec) {
first = first->next;
sec = sec->next;
}
// Push last k nodes in stack
while (first) {
st.push(first->data);
first = first->next;
}
// Last k nodes are reversed when pushed
// in stack. Pop all k elements of stack
// and print them.
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
return 0;
}
Java
// Java implementation to print
// the last k nodes of linked list
// in reverse order
import java.util.*;
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Stack to store data value of nodes.
Stack<Integer> st = new Stack<Integer>();
// Declare two pointers.
Node first = head, sec = head;
int cnt = 0;
// Move second pointer to kth node.
while (cnt < k)
{
sec = sec.next;
cnt++;
}
// Move first pointer to kth node from end
while (sec != null)
{
first = first.next;
sec = sec.next;
}
// Push last k nodes in stack
while (first != null)
{
st.push(first.data);
first = first.next;
}
// Last k nodes are reversed when pushed
// in stack. Pop all k elements of stack
// and print them.
while (!st.empty())
{
System.out.print(st.peek() + " ");
st.pop();
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 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 # Function to print the last k nodes # of linked list in reverse order def printLastKRev( head, k): # if list is empty if (head == None): return # Stack to store data value of nodes. st = [] # Declare two pointers. first = head sec = head cnt = 0 # Move second pointer to kth node. while (cnt < k) : sec = sec.next cnt = cnt + 1 # Move first pointer to kth node from end while (sec != None): first = first.next sec = sec.next # Push last k nodes in stack while (first != None): st.append(first.data) first = first.next # Last k nodes are reversed when pushed # in stack. Pop all k elements of stack # and print them. while (len(st)): print( st[-1], end= " ") st.pop() # 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 # print the last k nodes printLastKRev(head, k) # This code is contributed by Arnab Kundu
C#
// C# implementation to print
// the last k nodes of linked list
// in reverse order
using System;
using System.Collections.Generic;
class GFG
{
// Structure of a node
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Stack to store data value of nodes.
Stack<int> st = new Stack<int>();
// Declare two pointers.
Node first = head, sec = head;
int cnt = 0;
// Move second pointer to kth node.
while (cnt < k)
{
sec = sec.next;
cnt++;
}
// Move first pointer to kth node from end
while (sec != null)
{
first = first.next;
sec = sec.next;
}
// Push last k nodes in stack
while (first != null)
{
st.Push(first.data);
first = first.next;
}
// Last k nodes are reversed when pushed
// in stack. Pop all k elements of stack
// and print them.
while (st.Count != 0)
{
Console.Write(st.Peek() + " ");
st.Pop();
}
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to print
// the last k nodes of linked list
// in reverse order
// 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;
}
// Function to print the last k nodes
// of linked list in reverse order
function printLastKRev(head, k) {
// if list is empty
if (head == null) return;
// Stack to store data value of nodes.
var st = [];
// Declare two pointers.
var first = head,
sec = head;
var cnt = 0;
// Move second pointer to kth node.
while (cnt < k) {
sec = sec.next;
cnt++;
}
// Move first pointer to kth node from end
while (sec != null) {
first = first.next;
sec = sec.next;
}
// Push last k nodes in stack
while (first != null) {
st.push(first.data);
first = first.next;
}
// Last k nodes are reversed when pushed
// in stack. Pop all k elements of stack
// and print them.
while (st.length != 0) {
document.write(st[st.length - 1] + " ");
st.pop();
}
}
// 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);
var k = 4;
// print the last k nodes
printLastKRev(head, k);
</script>
Producción:
5 4 3 2
Complejidad temporal: O(N)
Espacio auxiliar: O(k)
Enfoque-2:
- Cuente el número de Nodes en la lista enlazada.
- Declare una array con el número de Nodes como su tamaño.
- Comience a almacenar el valor de los Nodes de la lista enlazada desde el final de la array, es decir, de manera inversa.
- Imprima valores k desde el inicio de la array.
C++
#include <iostream>
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) {
struct Node* cur = head;
while(cur != NULL){
count++;
cur = cur->next;
}
int arr[count], temp = count;
cur = head;
while(cur != NULL){
arr[--temp] = cur->data;
cur = cur->next;
}
for(int i = 0; i < k; i++)
cout << arr[i] << " ";
}
//
// 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);
head->next->next->next->next->next = getNode(10);
int k = 4, count = 0;
// print the last k nodes
printLastKRev(head, count, k);
return 0;
}
Java
// Java code implementation for above approach
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head,
int count, int k)
{
Node cur = head;
while(cur != null)
{
count++;
cur = cur.next;
}
int []arr = new int[count];
int temp = count;
cur = head;
while(cur != null)
{
arr[--temp] = cur.data;
cur = cur.next;
}
for(int i = 0; i < k; i++)
System.out.print(arr[i] + " ");
}
// 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);
head.next.next.next.next.next = getNode(10);
int k = 4, count = 0;
// print the last k nodes
printLastKRev(head, count, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 code implementation for above approach # Structure of a node class Node: def __init__(self, data): self.data = data self.next = None # Function to get a new node def getNode(data): # allocate space newNode = Node(data) return newNode # Function to print the last k nodes # of linked list in reverse order def printLastKRev(head, count,k): cur = head; while(cur != None): count += 1 cur = cur.next; arr = [0 for i in range(count)] temp = count; cur = head; while(cur != None): temp -= 1 arr[temp] = cur.data; cur = cur.next; for i in range(k): print(arr[i], end = ' ') # Driver code if __name__=='__main__': # 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); head.next.next.next.next.next = getNode(10); k = 4 count = 0; # print the last k nodes printLastKRev(head, count, k); # This code is contributed by rutvik_56
C#
// C# code implementation for above approach
using System;
class GFG
{
// Structure of a node
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;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head,
int count, int k)
{
Node cur = head;
while(cur != null)
{
count++;
cur = cur.next;
}
int []arr = new int[count];
int temp = count;
cur = head;
while(cur != null)
{
arr[--temp] = cur.data;
cur = cur.next;
}
for(int i = 0; i < k; i++)
Console.Write(arr[i] + " ");
}
// 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);
head.next.next.next.next.next = getNode(10);
int k = 4, count = 0;
// print the last k nodes
printLastKRev(head, count, k);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<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;
}
// Function to print the last k nodes
// of linked list in reverse order
function printLastKRev( head, count, k)
{
var cur = head;
while(cur != null)
{
count++;
cur = cur.next;
}
let arr = new Array(count);
let temp = count;
cur = head;
while(cur != null)
{
arr[--temp] = cur.data;
cur = cur.next;
}
for(let i = 0; i < k; i++)
document.write(arr[i] + " ");
}
// 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);
head.next.next.next.next.next = getNode(10);
let k = 4, count = 0;
// print the last k nodes
printLastKRev(head, count, k);
// This code is contributed b jana_sayantan
</script>
Producción:
10 5 4 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque-3: la idea es primero invertir la lista vinculada de forma iterativa como se explica en la siguiente publicación: Invertir una lista vinculada . Después de invertir, imprima los primeros k Nodes de la lista invertida. Después de imprimir, restaure la lista invirtiendo la lista nuevamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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 reverse the linked list.
Node* reverseLL(Node* head)
{
if (!head || !head->next)
return head;
Node *prev = NULL, *next = NULL, *curr = head;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to print the last k nodes
// of linked list in reverse order
void printLastKRev(Node* head, int k)
{
// if list is empty
if (!head)
return;
// Reverse linked list.
head = reverseLL(head);
Node* curr = head;
int cnt = 0;
// Print first k nodes of linked list.
while (cnt < k) {
cout << curr->data << " ";
cnt++;
curr = curr->next;
}
// Restore the list.
head = reverseLL(head);
}
// 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;
// print the last k nodes
printLastKRev(head, k);
return 0;
}
Java
// Java implementation to print the last k nodes
// of linked list in reverse order
import java.util.*;
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;
}
// Function to reverse the linked list.
static Node reverseLL(Node head)
{
if (head == null || head.next == null)
return head;
Node prev = null, next = null, curr = head;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Reverse linked list.
head = reverseLL(head);
Node curr = head;
int cnt = 0;
// Print first k nodes of linked list.
while (cnt < k)
{
System.out.print(curr.data + " ");
cnt++;
curr = curr.next;
}
// Restore the list.
head = reverseLL(head);
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to print the # last k nodes of linked list in # reverse order # Structure of a node class Node: def __init__(self, data): self.data = data self.next = None # Function to get a new node def getNode(data): # Allocate space newNode = Node(data) return newNode # Function to reverse the linked list. def reverseLL(head): if (not head or not head.next): return head prev = None next = None curr = head; while (curr): next = curr.next curr.next = prev prev = curr curr = next return prev # Function to print the last k nodes # of linked list in reverse order def printLastKRev(head, k): # If list is empty if (not head): return # Reverse linked list. head = reverseLL(head) curr = head cnt = 0 # Print first k nodes of linked list. while (cnt < k): print(curr.data, end = ' ') cnt += 1 curr = curr.next # Restore the list. head = reverseLL(head) # Driver code if __name__=='__main__': # 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 # Print the last k nodes printLastKRev(head, k) # This code is contributed by pratham76
C#
// 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;
}
// Function to reverse the linked list.
static Node reverseLL(Node head)
{
if (head == null || head.next == null)
return head;
Node prev = null, next = null, curr = head;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to print the last k nodes
// of linked list in reverse order
static void printLastKRev(Node head, int k)
{
// if list is empty
if (head == null)
return;
// Reverse linked list.
head = reverseLL(head);
Node curr = head;
int cnt = 0;
// Print first k nodes of linked list.
while (cnt < k)
{
Console.Write(curr.data + " ");
cnt++;
curr = curr.next;
}
// Restore the list.
head = reverseLL(head);
}
// 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;
// print the last k nodes
printLastKRev(head, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to print the last k nodes
// of linked list in reverse order
// Structure of a node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
// Function to get a new node
function getNode(data)
{
// allocate space
let newNode = new Node();
// put in data
newNode.data = data;
newNode.next = null;
return newNode;
}
// Function to reverse the linked list.
function reverseLL(head)
{
if (head == null || head.next == null)
return head;
let prev = null, next = null, curr = head;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to print the last k nodes
// of linked list in reverse order
function printLastKRev(head,k)
{
// if list is empty
if (head == null)
return;
// Reverse linked list.
head = reverseLL(head);
let curr = head;
let cnt = 0;
// Print first k nodes of linked list.
while (cnt < k)
{
document.write(curr.data + " ");
cnt++;
curr = curr.next;
}
// Restore the list.
head = reverseLL(head);
}
// Driver code
// Create list: 1->2->3->4->5
let 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;
// print the last k nodes
printLastKRev(head, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5 4 3 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)