a
Lista enlazada circular antes de ordenar:
LISTA VINCULADA CIRCULAR
Lista enlazada circular después de ordenar:
LISTA ENLAZADA CIRCULAR ORDENADA
Acercarse:
- Tome dos punteros: Actual apuntando a la cabeza del Node y Temp apuntando al siguiente Node de Actual.
- Ahora, para cada iteración, compare el valor del puntero actual con el valor del puntero temporal .
Aquí surgen dos casosCaso 1: si el valor de un puntero actual es mayor que el de un puntero temporal
Intercambie los valores de un puntero actual y un puntero temporal.
Mueva el puntero temporal al siguiente Node
Caso 2: si el valor de un puntero actual es menor o igual que el del puntero temporal
Mueva el puntero temporal al siguiente Node
- Ahora sigue haciendo esto hasta temp.next !=head of the list .
- Después de completar el paso 3, mueva el Actual al siguiente Node y repita los pasos 1,2,3.
- Cada iteración da como resultado la fijación del elemento más corto de la lista en su posición correcta.
- Repita los pasos anteriores hasta Actual. ¡Siguiente! = cabeza de lista.
Veamos cómo funciona esto para el primer Node de la lista enlazada circular dada
A continuación se muestra la implementación del enfoque anterior:
Java
// Java Program to Sort the Elements
// of the Circular Linked List
import java.io.*;
public class GFG {
// Stores Information about Node of List
public class Node {
int data;
Node next;
public Node(int data) { this.data = data; }
}
// Declaring Head of the Node
public Node head_of_node = null;
// A last pointer to help append values to our list
public Node last = null;
// Add method adds values to the end of the list
public void add(int data)
{
Node newNode = new Node(data);
if (head_of_node == null) {
head_of_node = newNode;
last = newNode;
newNode.next = head_of_node;
}
else {
last.next = newNode;
last = newNode;
last.next = head_of_node;
}
}
// Sort_List method sorts the circular
// linked list Using the algorithm
public void Sort_List()
{
// current pointer pointing to the head of the list
Node current = head_of_node;
// a temp pointer
Node temp = null;
// variable value helps in swap of the values
int value;
// this is the Algorithm discussed above
if (head_of_node == null) {
System.out.println("Your list is empty");
}
else {
while (current.next != head_of_node) {
temp = current.next;
while (temp != head_of_node) {
if (current.data > temp.data) {
value = current.data;
current.data = temp.data;
temp.data = value;
}
temp = temp.next;
}
current = current.next;
}
}
}
// Print_list method iterates through the list and
// prints the values stored in the list
public void Print_List()
{
Node current = head_of_node;
if (head_of_node == null) {
System.out.println("Your list is empty");
}
else {
do {
System.out.print(" " + current.data);
current = current.next;
} while (current != head_of_node);
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
GFG circular_list = new GFG();
circular_list.add(10);
circular_list.add(6);
circular_list.add(3);
circular_list.add(8);
circular_list.add(4);
System.out.print("Original List --> ");
circular_list.Print_List();
circular_list.Sort_List();
System.out.print("List after Sorting--> ");
circular_list.Print_List();
}
}
Original List --> 10 6 3 8 4 List after Sorting--> 3 4 6 8 10
Complejidad temporal: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por uchiha1101 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA