Encontrar la mediana en una lista enlazada ordenada

Posted on by Rudeus Greyrat

Dada Una lista enlazada ordenada de  N elementos. La tarea es encontrar la mediana en la lista ordenada ordenada dada.
Sabemos que la mediana en una array ordenada es el elemento central.

Procedimiento para encontrar la mediana de N números ordenados :  

if N is odd:
    median is N/2th element
else
    median is N/2th element + (N/2+1)th element

Ejemplos: 

Input : 1->2->3->4->5->NULL
Output : 3

Input : 1->2->3->4->5->6->NULL
Output : 3.5

Enfoque sencillo  

  1. Recorra la lista enlazada y cuente todos los elementos.
  2. si el recuento es impar, vuelva a recorrer la lista vinculada y encuentre el elemento n/2.
  3. si el conteo es par, vuelva a recorrer la lista enlazada y busque: 
    (n/2 elemento+ (n/2+1) elemento)/2

Nota : La solución anterior atraviesa la lista enlazada dos veces.

Enfoque eficiente : un enfoque eficiente es recorrer la lista usando dos punteros para encontrar el número de elementos. Vea el método 2 de esta publicación .
Podemos usar el algoritmo anterior para encontrar la mediana de la lista enlazada. Usando este algoritmo no necesitaremos contar el número de elementos: 

  1. si fast_ptr no es NULL, significa que la lista enlazada contiene elementos impares, simplemente imprimimos los datos de slow_ptr .
  2. de lo contrario, si fast_ptr llega a NULL, significa que la lista enlazada contiene un elemento par, creamos una copia de seguridad del Node anterior de slow_ptr e imprimimos (Node anterior de slow_ptr+ slow_ptr->data)/2

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ program to find median
// of a linked list
#include <bits/stdc++.h>
using namespace std;
 
// Link list node
struct Node {
    int data;
    struct Node* next;
};
 
/* Function to get the median of the linked list */
void printMidean(Node* head)
{
    Node* slow_ptr = head;
    Node* fast_ptr = head;
    Node* pre_of_slow = head;
 
    if (head != NULL) {
        while (fast_ptr != NULL && fast_ptr->next != NULL) {
 
            fast_ptr = fast_ptr->next->next;
 
            // previous of slow_ptr
            pre_of_slow = slow_ptr;
            slow_ptr = slow_ptr->next;
        }
 
        // if the below condition is true linked list
        // contain odd Node
        // simply return middle element
        if (fast_ptr != NULL)
            cout << "Median is : " << slow_ptr->data;
 
        // else linked list contain even element
        else
            cout << "Median is : "
                 << float(slow_ptr->data + pre_of_slow->data) / 2;
    }
}
 
/* 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)
{
    // allocate node
    Node* new_node = new 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;
}
 
// Driver Code
int main()
{
    // Start with the
    // empty list
    struct Node* head = NULL;
 
    // Use push() to construct
    // below list
    // 1->2->3->4->5->6
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
 
    // Check the count
    // function
    printMidean(head);
 
    return 0;
}

Java

// Java program to find median
// of a linked list
class GFG
{
 
    // Link list node
    static class Node
    {
 
        int data;
        Node next;
    };
 
    /* Function to get the median of the linked list */
    static void printMidean(Node head)
    {
        Node slow_ptr = head;
        Node fast_ptr = head;
        Node pre_of_slow = head;
 
        if (head != null)
        {
            while (fast_ptr != null && fast_ptr.next != null)
            {
 
                fast_ptr = fast_ptr.next.next;
 
                // previous of slow_ptr
                pre_of_slow = slow_ptr;
                slow_ptr = slow_ptr.next;
            }
 
            // if the below condition is true linked list
            // contain odd Node
            // simply return middle element
            if (fast_ptr != null)
            {
                System.out.print("Median is : " + slow_ptr.data);
            }
             
            // else linked list contain even element
            else
            {
                System.out.print("Median is : "
                        + (float) (slow_ptr.data + pre_of_slow.data) / 2);
            }
        }
    }
 
    /* 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. */
    static Node push(Node head_ref, int new_data)
    {
        // allocate node
        Node new_node = new 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;
        return head_ref;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Start with the
        // empty list
        Node head = null;
 
        // Use push() to construct
        // below list
        // 1.2.3.4.5.6
        head = push(head, 6);
        head = push(head, 5);
        head = push(head, 4);
        head = push(head, 3);
        head = push(head, 2);
        head = push(head, 1);
 
        // Check the count
        // function
        printMidean(head);
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find median
# of a linked list
class Node:
     
    def __init__(self, value):
         
        self.data = value
        self.next = None
     
class LinkedList:
 
    def __init__(self):
         
        self.head = None
 
    # Create Node and make linked list
    def push(self, new_data):
         
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
         
    # Function to get the median
    # of the linked list   
    def printMedian(self):
         
        slow_ptr = self.head
        fast_ptr = self.head
        pre_of_show = self.head
        count = 0
         
        while (fast_ptr != None and
               fast_ptr.next != None):
            fast_ptr = fast_ptr.next.next
             
            # Previous of slow_ptr
            pre_of_slow = slow_ptr
            slow_ptr = slow_ptr.next
        # If the below condition is true
        # linked list contain odd Node
        # simply return middle element   
        if (fast_ptr):
            print("Median is :", (slow_ptr.data))
             
        # Else linked list contain even element
        else:
            print("Median is :", (slow_ptr.data +
                                  pre_of_slow.data) / 2)
                                   
# Driver code
llist = LinkedList()
 
# Use push() to construct
# below list
# 1->2->3->4->5->6
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
 
# Check the count
# function
llist.printMedian()
 
# This code is contributed by grand_master

C#

// C# program to find median
// of a linked list
using System;
 
class GFG
{
 
    // Link list node
    class Node
    {
 
        public int data;
        public Node next;
    };
 
    /* Function to get the median
    of the linked list */
    static void printMidean(Node head)
    {
        Node slow_ptr = head;
        Node fast_ptr = head;
        Node pre_of_slow = head;
 
        if (head != null)
        {
            while (fast_ptr != null &&
                   fast_ptr.next != null)
            {
                fast_ptr = fast_ptr.next.next;
 
                // previous of slow_ptr
                pre_of_slow = slow_ptr;
                slow_ptr = slow_ptr.next;
            }
 
            // if the below condition is true linked list
            // contain odd Node
            // simply return middle element
            if (fast_ptr != null)
            {
                Console.Write("Median is : " +
                               slow_ptr.data);
            }
             
            // else linked list contain even element
            else
            {
                Console.Write("Median is : " +
                       (float)(slow_ptr.data +
                               pre_of_slow.data) / 2);
            }
        }
    }
 
    /* 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. */
    static Node push(Node head_ref, int new_data)
    {
        // allocate node
        Node new_node = new 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;
        return head_ref;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        // Start with the
        // empty list
        Node head = null;
 
        // Use push() to construct
        // below list
        // 1->2->3->4->5->6
        head = push(head, 6);
        head = push(head, 5);
        head = push(head, 4);
        head = push(head, 3);
        head = push(head, 2);
        head = push(head, 1);
 
        // Check the count
        // function
        printMidean(head);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to find median
// of a linked list
 
// A linked list node
class Node {
        constructor() {
                this.data = 0;
                this.next = null;
             }
        }
         
    /* Function to get the median of the linked list */
    function printMidean( head)
    {
        var slow_ptr = head;
        var fast_ptr = head;
        var pre_of_slow = head;
 
        if (head != null)
        {
            while (fast_ptr != null && fast_ptr.next != null)
            {
 
                fast_ptr = fast_ptr.next.next;
 
                // previous of slow_ptr
                pre_of_slow = slow_ptr;
                slow_ptr = slow_ptr.next;
            }
 
            // if the below condition is true linked list
            // contain odd Node
            // simply return middle element
            if (fast_ptr != null)
            {
                document.write("Median is : " + slow_ptr.data);
            }
             
            // else linked list contain even element
            else
            {
                document.write("Median is : "
                        +  (slow_ptr.data + pre_of_slow.data) / 2);
            }
        }
    }
 
    /* 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. */
    function push( head_ref,  new_data)
    {
        // allocate node
        var new_node = new 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;
        return head_ref;
    }
 
 
// Driver Code
 
// Start with the
// empty list
var head = null;
 
// Use push() to construct
// below list
// 1.2.3.4.5.6
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
 
// Check the count
// function
printMidean(head);
 
// This code is contributed by jana_sayantan.
</script>
Producción: 

Median is : 3.5

 

Publicación traducida automáticamente

Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *