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.
Método 2:
recorrer la lista enlazada usando 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:
Java
// Java program to find middle of // the linked list class LinkedList { // Head of linked list Node head; // Linked list node class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to print middle of // the 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; } System.out.println("The middle element is [" + slow_ptr.data + "]"); } } // 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"); } // Driver code 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
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 es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
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 de mitad a mitad->siguiente 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.
Java
// Java program to implement the // above approach 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
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 es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
¡ Consulte el artículo completo sobre Encontrar el medio de una lista vinculada dada para obtener más detalles!
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