Gegeben Eine sortierte verkettete Liste von  Elementen. Die Aufgabe besteht darin, den Median in der gegebenen sortierten verketteten Liste zu finden.
Wir wissen, dass der Median in einem sortierten Array das mittlere Element ist.

Verfahren zum Finden des Medians von N sortierten Zahlen :  

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

Beispiele: 

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

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

Einfacher Ansatz  

1. Durchlaufen Sie die verkettete Liste und zählen Sie alle Elemente.
2. Wenn die Anzahl ungerade ist, durchqueren Sie die verknüpfte Liste erneut und finden Sie das n/2-te Element.
3. Wenn die Anzahl gerade ist, durchlaufe die verknüpfte Liste erneut und finde: 
   (n/2-tes Element + (n/2+1)-tes Element)/2

Hinweis : Die obige Lösung durchläuft die verknüpfte Liste zweimal.

Effizienter Ansatz : Ein effizienter Ansatz besteht darin, die Liste unter Verwendung von zwei Zeigern zu durchlaufen, um die Anzahl der Elemente zu finden. Siehe Methode 2 dieses Beitrags .
Wir können den obigen Algorithmus verwenden, um den Median der verknüpften Liste zu finden. Mit diesem Algorithmus müssen wir die Anzahl der Elemente nicht zählen: 

1. Wenn der fast_ptr Not NULL ist, bedeutet dies, dass die verknüpfte Liste ein ungerades Element enthält. Wir drucken einfach die Daten des slow_ptr .
2. Andernfalls, wenn fast_ptr NULL erreicht, bedeutet dies, dass die verknüpfte Liste ein gerades Element enthält. Wir erstellen eine Sicherung des vorherigen Nodes von slow_ptr und drucken (vorheriger Node von slow_ptr + slow_ptr-> data)/2

Unten ist die Implementierung des obigen Ansatzes:  

// 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 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 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 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# 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

<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>

Median: 3,5

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .