Dada una lista enlazada individualmente, busque el centro de la lista enlazada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la salida debería ser 3.
Si hay Nodes pares, entonces habría dos Nodes intermedios, necesitamos imprimir el segundo intermedio. elemento. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5->6, entonces la salida debería ser 4.
Método 1: recorrer toda la lista enlazada y contar el no. de Nodes Ahora recorra la lista nuevamente hasta la cuenta/2 y devuelva el Node en la cuenta/2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
class NodeOperation {
public:
// Function to add a new node
void pushNode(class Node** head_ref, int data_val)
{
// Allocate node
class Node* new_node = new Node();
// Put in the data
new_node->data = data_val;
// 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;
}
// A utility function to print a given linked list
void printNode(class Node* head)
{
while (head != NULL) {
cout << head->data << "->";
head = head->next;
}
cout << "NULL" << endl;
}
/* Utility Function to find length of linked list */
int getLen(class Node* head)
{
int len = 0;
class Node* temp = head;
while (temp) {
len++;
temp = temp->next;
}
return len;
}
void printMiddle(class Node* head)
{
if (head) {
// find length
int len = getLen(head);
class Node* temp = head;
// trvaers till we reached half of length
int midIdx = len / 2;
while (midIdx--) {
temp = temp->next;
}
// temp will be storing middle element
cout << "The middle element is [" << temp->data
<< "]" << endl;
}
}
};
// Driver Code
int main()
{
class Node* head = NULL;
class NodeOperation* temp = new NodeOperation();
for (int i = 5; i > 0; i--) {
temp->pushNode(&head, i);
temp->printNode(head);
temp->printMiddle(head);
}
return 0;
}
// This code is contributed by Tapesh(tapeshdua420)
Java
// Java Program for the above approach
class GFG {
Node head;
/*Creating a new Node*/
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
/*Function to add a new Node*/
public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
/*Displaying the elements in the list*/
public void printNode()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.print("Null"+"\n");
}
/*Finding the length of the list.*/
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
/*Printing the middle element of the list.*/
public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print("The middle element is ["
+ temp.data + "]");
System.out.println();
}
}
public static void main(String[] args)
{
GFG list = new GFG();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
list.printNode();
list.printMiddle();
}
}
}
// This Code is contributed by lokesh (lokeshmvs21).
Python3
# Python program for the above approach
class Node:
def __init__(self, data):
self.data = data
self.next = None
class NodeOperation:
# Function to add a new node
def pushNode(self, head_ref, data_val):
# Allocate node and put in the data
new_node = Node(data_val)
# 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
return head_ref
# A utility function to print a given linked list
def printNode(self, head):
while (head != None):
print('%d->' % head.data, end="")
head = head.next
print("NULL")
''' Utility Function to find length of linked list '''
def getLen(self, head):
temp = head
len = 0
while (temp != None):
len += 1
temp = temp.next
return len
def printMiddle(self, head):
if head != None:
# find length
len = self.getLen(head)
temp = head
# traverse till we reached half of length
midIdx = len // 2
while midIdx != 0:
temp = temp.next
midIdx -= 1
# temp will be storing middle element
print('The middle element is [%d]' % temp.data)
# Driver Code
head = None
temp = NodeOperation()
for i in range(5, 0, -1):
head = temp.pushNode(head, i)
temp.printNode(head)
temp.printMiddle(head)
# This code is contributed by Tapesh(tapeshdua420)
Producción
5->NULL The middle element is [5] 4->5->NULL The middle element is [5] 3->4->5->NULL The middle element is [4] 2->3->4->5->NULL The middle element is [4] 1->2->3->4->5->NULL The middle element is [3]
Complejidad de tiempo : O (n) donde n no es ningún Node en la lista vinculada
Espacio Auxiliar: O(1)
Método 2: recorrer la lista enlazada utilizando dos punteros. Mueva un puntero por uno y los otros punteros por dos. Cuando el puntero rápido llegue al final, el puntero lento llegará a la mitad de la lista enlazada.
La siguiente imagen muestra cómo funciona la función printMiddle en el código:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
class Node{
public:
int data;
Node *next;
};
class NodeOperation{
public:
// Function to add a new node
void pushNode(class Node** head_ref,int data_val){
// Allocate node
class Node *new_node = new Node();
// Put in the data
new_node->data = data_val;
// 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;
}
// A utility function to print a given linked list
void printNode(class Node *head){
while(head != NULL){
cout <<head->data << "->";
head = head->next;
}
cout << "NULL" << endl;
}
void printMiddle(class Node *head){
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
if (head!=NULL)
{
while (fast_ptr != NULL && fast_ptr->next != NULL)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
cout << "The middle element is [" << slow_ptr->data << "]" << endl;
}
}
};
// Driver Code
int main(){
class Node *head = NULL;
class NodeOperation *temp = new NodeOperation();
for(int i=5; i>0; i--){
temp->pushNode(&head, i);
temp->printNode(head);
temp->printMiddle(head);
}
return 0;
}
C
// C program to find middle of linked list
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Function to get the middle of the linked list*/
void printMiddle(struct Node *head)
{
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
if (head!=NULL)
{
while (fast_ptr != NULL && fast_ptr->next != NULL)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
printf("The middle element is [%d]\n\n", slow_ptr->data);
}
}
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;
}
// A utility function to print a given linked list
void printList(struct Node *ptr)
{
while (ptr != NULL)
{
printf("%d->", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
int i;
for (i=5; i>0; i--)
{
push(&head, i);
printList(head);
printMiddle(head);
}
return 0;
}
Java
// Java program to find middle of linked list
class LinkedList
{
Node head; // head of linked list
/* Linked list node */
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to print middle of linked list */
void printMiddle()
{
Node slow_ptr = head;
Node fast_ptr = head;
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println("The middle element is [" +
slow_ptr.data + "] \n");
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* This function prints contents of linked list
starting from the given node */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+"->");
tnode = tnode.next;
}
System.out.println("NULL");
}
public static void main(String [] args)
{
LinkedList llist = new LinkedList();
for (int i=5; i>0; --i)
{
llist.push(i);
llist.printList();
llist.printMiddle();
}
}
}
// This code is contributed by Rajat Mishra
C#
// C# program to find middle of linked list
using System;
class LinkedList{
// Head of linked list
Node head;
// Linked list node
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// Function to print middle of linked list
void printMiddle()
{
Node slow_ptr = head;
Node fast_ptr = head;
if (head != null)
{
while (fast_ptr != null &&
fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
Console.WriteLine("The middle element is [" +
slow_ptr.data + "] \n");
}
}
// Inserts a new Node at front of the list.
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// This function prints contents of linked
// list starting from the given node
public void printList()
{
Node tnode = head;
while (tnode != null)
{
Console.Write(tnode.data + "->");
tnode = tnode.next;
}
Console.WriteLine("NULL");
}
// Driver code
static public void Main()
{
LinkedList llist = new LinkedList();
for(int i = 5; i > 0; --i)
{
llist.push(i);
llist.printList();
llist.printMiddle();
}
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program to find middle of linked list
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class contains a Node object
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Print the linked list
def printList(self):
node = self.head
while node:
print(str(node.data) + "->", end="")
node = node.next
print("NULL")
# Function that returns middle.
def printMiddle(self):
# Initialize two pointers, one will go one step a time (slow), another two at a time (fast)
slow = self.head
fast = self.head
# Iterate till fast's next is null (fast reaches end)
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# return the slow's data, which would be the middle element.
print("The middle element is ", slow.data)
# Code execution starts here
if __name__=='__main__':
# Start with the empty list
llist = LinkedList()
for i in range(5, 0, -1):
llist.push(i)
llist.printList()
llist.printMiddle()
# Code is contributed by Kumar Shivam (kshivi99)
Javascript
<script>
// JavaScript program to find
// middle of linked list
var head; // head of linked list
/* Linked list node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/* Function to print middle
of linked list */
function printMiddle()
{
var slow_ptr = head;
var fast_ptr = head;
if (head != null)
{
while (fast_ptr != null &&
fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
document.write(
"The middle element is [" + slow_ptr.data + "] <br/><br/>"
);
}
}
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*
* This function prints contents of linked
list starting from the given node
*/
function printList() {
var tnode = head;
while (tnode != null) {
document.write(tnode.data + "->");
tnode = tnode.next;
}
document.write("NULL<br/>");
}
for (i = 5; i > 0; --i) {
push(i);
printList();
printMiddle();
}
// This code is contributed by todaysgaurav
</script>
Producción
5->NULL The middle element is [5] 4->5->NULL The middle element is [5] 3->4->5->NULL The middle element is [4] 2->3->4->5->NULL The middle element is [4] 1->2->3->4->5->NULL The middle element is [3]
Complejidad temporal: O(N), ya que estamos recorriendo la lista una sola vez.
Espacio Auxiliar: O(1), Como espacio extra constante se utiliza.
Método 3: Inicialice el elemento medio como cabeza e inicialice un contador como 0. Recorra la lista desde la cabeza, mientras recorre incremente el contador y cambie mid a mid->next siempre que el contador sea impar. Entonces, el medio se moverá solo la mitad de la longitud total de la lista.
Gracias a Narendra Kangralkar por sugerir este método.
C++
#include <bits/stdc++.h>
using namespace std;
// Link list node
struct node
{
int data;
struct node* next;
};
// Function to get the middle of
// the linked list
void printMiddle(struct node* head)
{
int count = 0;
struct node* mid = head;
while (head != NULL)
{
// Update mid, when 'count'
// is odd number
if (count & 1)
mid = mid->next;
++count;
head = head->next;
}
// If empty list is provided
if (mid != NULL)
printf("The middle element is [%d]\n\n",
mid->data);
}
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;
}
// A utility function to print
// a given linked list
void printList(struct node* ptr)
{
while (ptr != NULL)
{
printf("%d->", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}
// Driver code
int main()
{
// Start with the empty list
struct node* head = NULL;
int i;
for(i = 5; i > 0; i--)
{
push(&head, i);
printList(head);
printMiddle(head);
}
return 0;
}
// This code is contributed by ac121102
C
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct node {
int data;
struct node* next;
};
/* Function to get the middle of the linked list*/
void printMiddle(struct node* head)
{
int count = 0;
struct node* mid = head;
while (head != NULL) {
/* update mid, when 'count' is odd number */
if (count & 1)
mid = mid->next;
++count;
head = head->next;
}
/* if empty list is provided */
if (mid != NULL)
printf("The middle element is [%d]\n\n", mid->data);
}
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;
}
// A utility function to print a given linked list
void printList(struct node* ptr)
{
while (ptr != NULL) {
printf("%d->", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
int i;
for (i = 5; i > 0; i--) {
push(&head, i);
printList(head);
printMiddle(head);
}
return 0;
}
Java
class GFG{
static Node head;
// Link list node
class Node
{
int data;
Node next;
// Constructor
public Node(Node next, int data)
{
this.data = data;
this.next = next;
}
}
// Function to get the middle of
// the linked list
void printMiddle(Node head)
{
int count = 0;
Node mid = head;
while (head != null)
{
// Update mid, when 'count'
// is odd number
if ((count % 2) == 1)
mid = mid.next;
++count;
head = head.next;
}
// If empty list is provided
if (mid != null)
System.out.println("The middle element is [" +
mid.data + "]\n");
}
void push(Node head_ref, int new_data)
{
// Allocate node
Node new_node = new Node(head_ref, new_data);
// Move the head to point to the new node
head = new_node;
}
// A utility function to print a
// given linked list
void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + "-> ");
head = head.next;
}
System.out.println("null");
}
// Driver code
public static void main(String[] args)
{
GFG ll = new GFG();
for(int i = 5; i > 0; i--)
{
ll.push(head, i);
ll.printList(head);
ll.printMiddle(head);
}
}
}
// This code is contributed by mark_3
Python3
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class contains a Node object
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Print the linked list
def printList(self):
node = self.head
while node:
print(str(node.data) + "->", end = "")
node = node.next
print("NULL")
# Function to get the middle of
# the linked list
def printMiddle(self):
count = 0
mid = self.head
heads = self.head
while(heads != None):
# Update mid, when 'count'
# is odd number
if count&1:
mid = mid.next
count += 1
heads = heads.next
# If empty list is provided
if mid!=None:
print("The middle element is ", mid.data)
# Code execution starts here
if __name__=='__main__':
# Start with the empty list
llist = LinkedList()
for i in range(5, 0, -1):
llist.push(i)
llist.printList()
llist.printMiddle()
# This Code is contributed by Manisha_Ediga
C#
using System;
public class GFG
{
static Node head;
// Link list node
public
class Node {
public
int data;
public
Node next;
// Constructor
public Node(Node next, int data) {
this.data = data;
this.next = next;
}
}
// Function to get the middle of
// the linked list
void printMiddle(Node head) {
int count = 0;
Node mid = head;
while (head != null) {
// Update mid, when 'count'
// is odd number
if ((count % 2) == 1)
mid = mid.next;
++count;
head = head.next;
}
// If empty list is provided
if (mid != null)
Console.WriteLine("The middle element is [" + mid.data + "]\n");
}
public void Push(Node head_ref, int new_data) {
// Allocate node
Node new_node = new Node(head_ref, new_data);
// Move the head to point to the new node
head = new_node;
}
// A utility function to print a
// given linked list
void printList(Node head) {
while (head != null) {
Console.Write(head.data + "-> ");
head = head.next;
}
Console.WriteLine("null");
}
// Driver code
public static void Main(String[] args) {
GFG ll = new GFG();
for (int i = 5; i > 0; i--) {
ll.Push(head, i);
ll.printList(head);
ll.printMiddle(head);
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
var head=null;
// Link list node
class Node {
constructor(next,val) {
this.data = val;
this.next = next;
}
}
// Function to get the middle of
// the linked list
function printMiddle(head) {
var count = 0;
var mid = head;
while (head != null) {
// Update mid, when 'count'
// is odd number
if ((count % 2) == 1)
mid = mid.next;
++count;
head = head.next;
}
// If empty list is provided
if (mid != null)
document.write("The middle element is [" + mid.data + "]<br/><br/>");
}
function push(head_ref , new_data) {
// Allocate node
var new_node = new Node(head_ref, new_data);
// Move the head to point to the new node
head = new_node;
return head;
}
// A utility function to print a
// given linked list
function printList(head) {
while (head != null) {
document.write(head.data + "-> ");
head = head.next;
}
document.write("null<br/>");
}
// Driver code
for (i = 5; i > 0; i--) {
head= push(head, i);
printList(head);
printMiddle(head);
}
// This code contributed by gauravrajput1
</script>
Producción
5->NULL The middle element is [5] 4->5->NULL The middle element is [5] 3->4->5->NULL The middle element is [4] 2->3->4->5->NULL The middle element is [4] 1->2->3->4->5->NULL The middle element is [3]
Complejidad temporal: O(N), ya que estamos recorriendo la lista una vez.
Espacio Auxiliar: O(1), Como espacio extra constante se utiliza.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA