Dada una lista enlazada individualmente, encuentre el medio de la lista enlazada y establezca el Node medio de la lista enlazada al principio de la lista enlazada.
Ejemplos:
Input: 1 2 3 4 5 Output: 3 1 2 4 5 Input: 1 2 3 4 5 6 Output: 4 1 2 3 5 6
La idea es encontrar primero el medio de una lista enlazada usando dos punteros , el primero se mueve uno a la vez y el segundo se mueve dos a la vez. Cuando el segundo puntero llega al final, el primero llega al medio. También realizamos un seguimiento del anterior del primer puntero para que podamos eliminar el Node medio de su posición actual y convertirlo en la cabeza.
Java
// Java program to make middle node
// as head of Linked list
public class GFG
{
// Link list node
static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
static Node head;
/* Function to get the middle and
set at beginning of the linked list*/
static void setMiddleHead()
{
if (head == null)
return;
// To traverse list nodes one
// by one
Node one_node = head;
// To traverse list nodes by
// skipping one.
Node two_node = head;
// To keep track of previous of middle
Node prev = null;
while (two_node != null &&
two_node.next != null)
{
// For previous node of middle node
prev = one_node;
// Move one node each time
two_node = two_node.next.next;
// Move two node each time
one_node = one_node.next;
}
// Set middle node at head
prev.next = prev.next.next;
one_node.next = head;
head = one_node;
}
// To insert a node at the beginning
// of linked list.
static void push(int new_data)
{
// Allocate node
Node new_node = new Node(new_data);
// Link the old list off the new node
new_node.next = head;
// Move the head to point to the
// new node
head = new_node;
}
// A function to print a given linked list
static void printList(Node ptr)
{
while (ptr != null)
{
System.out.print(ptr.data + " ");
ptr = ptr.next;
}
System.out.println();
}
// Driver function
public static void main(String args[])
{
// Create a list of 5 nodes
head = null;
int i;
for (i = 5; i > 0; i--)
push(i);
System.out.print(" list before: ");
printList(head);
setMiddleHead();
System.out.print(" list After: ");
printList(head);
}
}
// This code is contributed by Sumit Ghosh
Producción:
list before: 1 2 3 4 5 list After : 3 1 2 4 5
Complejidad de tiempo : O(n) donde n es el número total de Nodes en la lista enlazada.
Complejidad espacial : O (1) ya que usa espacio constante
¡ Consulte el artículo completo sobre Hacer la cabeza del Node medio en una lista vinculada 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