Encuentra el medio de una lista enlazada dada

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:

middle-of-a-given-linked-list-in-C-and-Java1

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

Deja una respuesta

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