Dada una Lista Enlazada y un número K. La tarea es imprimir el valor del K-ésimo Node desde el medio hacia el principio de la Lista. Si no existe tal elemento, imprima «-1».
Nota : La posición del Node medio es: (n/2)+1, donde n es el número total de Nodes en la lista.
Ejemplos :
Input : List is 1->2->3->4->5->6->7
K= 2
Output : 2
Input : list is 7->8->9->10->11->12
K = 3
Output : 7
Recorra la Lista de principio a fin y cuente el número total de Nodes. Ahora, supongamos que 
es el número total de Nodes en la Lista. Por lo tanto, el Node medio estará en la posición (n/2)+1. Ahora, queda la tarea de imprimir el Node en (n/2 + 1 – k) la ésima posición desde el encabezado de la Lista .
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to find kth node from middle
// towards Head of the Linked List
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node {
int data;
struct Node* next;
};
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
void push(struct Node** head_ref,
int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to count number of nodes
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
// Function to get the kth node from the mid
// towards begin of the linked list
int printKthfrommid(struct Node* head_ref, int k)
{
// Get the count of total number of
// nodes in the linked list
int n = getCount(head_ref);
int reqNode = ((n / 2 + 1) - k);
// If no such node exists, return -1
if (reqNode <= 0) {
return -1;
}
// Find node at position reqNode
else {
struct Node* current = head_ref;
// the index of the
// node we're currently
// looking at
int count = 1;
while (current != NULL) {
if (count == reqNode)
return (current->data);
count++;
current = current->next;
}
}
}
// Driver code
int main()
{
// start with empty list
struct Node* head = NULL;
int k = 2;
// create linked list
// 1->2->3->4->5->6->7
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << printKthfrommid(head, 2);
return 0;
}
Java
// Java program to find Kth node from mid
// of a linked list in single traversal
// Linked list node
class Node
{
int data;
Node next;
Node(int d)
{
this.data = d;
this.next = null;
}
}
class LinkedList
{
Node start;
LinkedList()
{
start = null;
}
// Function to push node at head
public void push(int data)
{
if(this.start == null)
{
Node temp = new Node(data);
this.start = temp;
}
else
{
Node temp = new Node(data);
temp.next = this.start;
this.start = temp;
}
}
//method to get the count of node
public int getCount(Node start)
{
Node temp = start;
int cnt = 0;
while(temp != null)
{
temp = temp.next;
cnt++;
}
return cnt;
}
// Function to get the kth node from the mid
// towards begin of the linked list
public int printKthfromid(Node start, int k)
{
// Get the count of total number of
// nodes in the linked list
int n = getCount(start);
int reqNode = ((n + 1) / 2) - k;
// If no such node exists, return -1
if(reqNode <= 0)
return -1;
else
{
Node current = start;
int count = 1,ans = 0;
while (current != null)
{
if (count == reqNode)
{
ans = current.data;
break;
}
count++;
current = current.next;
}
return ans;
}
}
// Driver code
public static void main(String[] args)
{
// create linked list
// 1->2->3->4->5->6->7
LinkedList ll = new LinkedList();
ll.push(7);
ll.push(6);
ll.push(5);
ll.push(4);
ll.push(3);
ll.push(2);
ll.push(1);
System.out.println(ll.printKthfromid(ll.start, 2));
}
}
// This Code is contributed by Adarsh_Verma
Python3
# Python3 program to find kth node from # middle towards Head of the Linked List # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data self.next = None # Function to insert a node at the # beginning of the linked list def push(head, data): if not head: # Return new node return Node(data) # allocate node new_node = Node(data) # link the old list to the new node new_node.next = head # move the head to point # to the new node head = new_node return head # Function to count number of nodes def getCount(head): count = 0 # Initialize count current = head # Initialize current while (current ): count = count + 1 current = current.next return count # Function to get the kth node from the mid # towards begin of the linked list def printKthfrommid(head_ref, k): # Get the count of total number of # nodes in the linked list n = getCount(head_ref) reqNode = int((n / 2 + 1) - k) # If no such node exists, return -1 if (reqNode <= 0) : return -1 # Find node at position reqNode else : current = head_ref # the index of the # node we're currently # looking at count = 1 while (current) : if (count == reqNode): return (current.data) count = count + 1 current = current.next # Driver Code if __name__=='__main__': # start with empty list head = None k = 2 # create linked list # 1.2.3.4.5.6.7 head = push(head, 7) head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) print(printKthfrommid(head, 2)) # This code is contributed by Arnab Kundu
C#
// C# program to find Kth node from mid
// of a linked list in single traversal
using System;
// Linked list node
public class Node
{
public int data;
public Node next;
public Node(int d)
{
this.data = d;
this.next = null;
}
}
public class LinkedList
{
Node start;
LinkedList()
{
start = null;
}
// Function to push node at head
public void push(int data)
{
if(this.start == null)
{
Node temp = new Node(data);
this.start = temp;
}
else
{
Node temp = new Node(data);
temp.next = this.start;
this.start = temp;
}
}
//method to get the count of node
public int getCount(Node start)
{
Node temp = start;
int cnt = 0;
while(temp != null)
{
temp = temp.next;
cnt++;
}
return cnt;
}
// Function to get the kth node from the mid
// towards begin of the linked list
public int printKthfromid(Node start, int k)
{
// Get the count of total number of
// nodes in the linked list
int n = getCount(start);
int reqNode = ((n + 1) / 2) - k;
// If no such node exists, return -1
if(reqNode <= 0)
return -1;
else
{
Node current = start;
int count = 1,ans = 0;
while (current != null)
{
if (count == reqNode)
{
ans = current.data;
break;
}
count++;
current = current.next;
}
return ans;
}
}
// Driver code
public static void Main(String[] args)
{
// create linked list
// 1->2->3->4->5->6->7
LinkedList ll = new LinkedList();
ll.push(7);
ll.push(6);
ll.push(5);
ll.push(4);
ll.push(3);
ll.push(2);
ll.push(1);
Console.WriteLine(ll.printKthfromid(ll.start, 2));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find Kth node from mid
// of a linked list in single traversal
// Linked list node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var start = null;
// Function to push node at head
function push(data) {
if (this.start == null)
{
temp = new Node(data);
this.start = temp;
}
else
{
temp = new Node(data);
temp.next = this.start;
this.start = temp;
}
}
// method to get the count of node
function getCount( start) {
temp = start;
var cnt = 0;
while (temp != null) {
temp = temp.next;
cnt++;
}
return cnt;
}
// Function to get the kth node from the mid
// towards begin of the linked list
function printKthfromid( start , k)
{
// Get the count of total number of
// nodes in the linked list
var n = getCount(start);
var reqNode = ((n + 1) / 2) - k;
// If no such node exists, return -1
if (reqNode <= 0)
return -1;
else {
current = start;
var count = 1, ans = 0;
while (current != null) {
if (count == reqNode) {
ans = current.data;
break;
}
count++;
current = current.next;
}
return ans;
}
}
// Driver code
// create linked list
// 1->2->3->4->5->6->7
push(7);
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
document.write(printKthfromid(start, 2));
// This code is contributed by aashish1995
</script>
Producción
2
Complejidad temporal : O(n), donde n es la longitud de la lista.
Espacio Auxiliar : O(1)
Método 2:
Este método se enfoca en encontrar el K-ésimo Node desde el medio hacia el comienzo de la Lista usando dos punteros.
Requisito previo: método de dos punteros en https://www.geeksforgeeks.org/write-ac-function-to-print-the-middle-of-the-linked-list/
Recorra la lista enlazada utilizando dos punteros denominados lento y rápido. Mueva el puntero rápido B veces si llega al final, entonces no hay respuesta, imprima «-1»; de lo contrario, comience a mover los punteros rápido y lento simultáneamente cuando el puntero rápido llegue al final, la respuesta será el valor del puntero lento.
A continuación se muestra la implementación de la idea anterior:
C++
// Using two pointers
// CPP program to find kth node from middle
// towards Head of the Linked List
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node {
int data;
struct Node* next;
};
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
void push(struct Node** head_ref,
int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to get the kth node from the mid
// towards begin of the linked list
int printKthfrommid(struct Node* head_ref, int k)
{
struct Node* slow = head_ref;
struct Node* fast = head_ref; // initializing fast and slow pointers
for( int i = 0 ; i < k ; i++ )
{
if(fast && fast->next)
{
fast = fast->next->next; // moving the fast pointer
}
else
{
return -1; // If no such node exists, return -1
}
}
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow->data;
}
// Driver code
int main()
{
// start with empty list
struct Node* head = NULL;
int k = 2;
// create linked list
// 1->2->3->4->5->6->7
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << printKthfrommid(head, 2);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
// Linked list node
class Node {
int data;
Node next;
}
class GFG {
public Node head = null;
/* Given a reference (pointer to pointer) to the head of
* a list and an int, push a new node on the front of
* the list. */
public void push(int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
// Function to get the kth node from the mid towards
// begin of the linked list
public int printKthfrommid(int k)
{
// initializing fast and slow pointers
Node slow = head;
Node fast = head;
for (int i = 0; i < k; i++) {
if (fast != null && fast.next != null) {
fast = fast.next
.next; // moving the fast pointer
}
else {
return -1; // If no such node exists, return
// -1
}
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
}
public static void main(String[] args)
{
GFG ll = new GFG();
// create linked list
// 1->2->3->4->5->6->7
ll.push(7);
ll.push(6);
ll.push(5);
ll.push(4);
ll.push(3);
ll.push(2);
ll.push(1);
int k = 2;
System.out.print(ll.printKthfrommid(k));
}
}
// This code is contributed by lokeshmvs21.
Producción
2
Complejidad temporal: O(n), donde n es la longitud de la lista.
Espacio Auxiliar: O(1)