A menudo se prefiere la ordenación por combinación para ordenar una lista vinculada. El lento rendimiento de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como la ordenación rápida) funcionen mal y otros (como la ordenación heap) sean completamente imposibles.
Deje que head sea el primer Node de la lista enlazada que se ordenará y headRef sea el puntero a head. Tenga en cuenta que necesitamos una referencia al encabezado en MergeSort() ya que la implementación a continuación cambia los siguientes enlaces para ordenar las listas vinculadas (no los datos en los Nodes), por lo que el Node principal debe cambiarse si los datos en el encabezado original no son los valor más pequeño en la lista enlazada.
MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List
then return.
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
MergeSort(a);
MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here)
and update the head pointer using headRef.
*headRef = SortedMerge(a, b);
Javascript
<script>
// Javascript program to
// illustrate merge sorted
// of linkedList
var head = null;
// node a, b;
class node {
constructor(val) {
this.val = val;
this.next = null;
}
}
function sortedMerge( a, b)
{
var result = null;
/* Base cases */
if (a == null)
return b;
if (b == null)
return a;
/* Pick either a or b, and recur */
if (a.val <= b.val) {
result = a;
result.next = sortedMerge(a.next, b);
} else {
result = b;
result.next = sortedMerge(a, b.next);
}
return result;
}
function mergeSort( h) {
// Base case : if head is null
if (h == null || h.next == null) {
return h;
}
// get the middle of the list
var middle = getMiddle(h);
var nextofmiddle = middle.next;
// set the next of middle node to null
middle.next = null;
// Apply mergeSort on left list
var left = mergeSort(h);
// Apply mergeSort on right list
var right = mergeSort(nextofmiddle);
// Merge the left and right lists
var sortedlist = sortedMerge(left, right);
return sortedlist;
}
// Utility function to get the middle
// of the linked list
function getMiddle( head) {
if (head == null)
return head;
var slow = head, fast = head;
while (fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
function push(new_data) {
/* allocate node */
var 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;
}
// Utility function to print the linked list
function printList( headref) {
while (headref != null) {
document.write(headref.val + " ");
headref = headref.next;
}
}
/*
Let us create a unsorted linked
list to test the functions
created. The list shall be
a: 2->3->20->5->10->15
*/
push(15);
push(10);
push(5);
push(20);
push(3);
push(2);
// Apply merge Sort
head = mergeSort(head);
document.write("
Sorted Linked List is:
");
printList(head);
// This code contributed by umadevi9616
</script>
Producción:
Sorted Linked List is: 2 3 5 10 15 20
Complejidad de tiempo: O(n*log n)
Complejidad espacial: O(n*log n)
Enfoque 2: este enfoque es más simple y utiliza el espacio log n.
mergeSort():
- Si el tamaño de la lista enlazada es 1, devuelve la cabeza
- Encuentre medio usando el enfoque de la Turtle y la liebre
- Guarde el siguiente de mid en head2, es decir, la lista de subenlaces correctos.
- Ahora haz que el siguiente punto medio sea nulo.
- Llame recursivamente a mergeSort() en la lista subvinculada izquierda y derecha y almacene el nuevo encabezado de la lista vinculada izquierda y derecha.
- Llame a merge() dados los argumentos nuevos encabezados de listas subvinculadas izquierda y derecha y almacene el encabezado final devuelto después de la fusión.
- Devuelve el encabezado final de la lista enlazada fusionada.
fusionar (cabeza1, cabeza2):
- Tome un puntero, digamos fusionado, para almacenar la lista fusionada en él y almacene un Node ficticio en él.
- Tome una temperatura de puntero y asígnele fusionar.
- Si los datos de head1 son menores que los datos de head2, entonces, almacene head1 en el siguiente de temp y mueva head1 al siguiente de head1.
- De lo contrario, almacene head2 en el siguiente de temp y mueva head2 al siguiente de head2.
- Mover temp al siguiente de temp.
- Repita los pasos 3, 4 y 5 hasta que head1 no sea igual a nulo y head2 no sea igual a nulo.
- Ahora agregue los Nodes restantes de la primera o la segunda lista vinculada a la lista vinculada fusionada.
- Devuelve el siguiente de fusionado (que ignorará el maniquí y devolverá el encabezado de la lista enlazada fusionada final)
Javascript
<script>
// JavaScript program for the above approach
// Node Class
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to merge sort
function mergeSort(head) {
if (head.next == null)
return head;
var mid = findMid(head);
var head2 = mid.next;
mid.next = null;
var newHead1 = mergeSort(head);
var newHead2 = mergeSort(head2);
var finalHead = merge(newHead1, newHead2);
return finalHead;
}
// Function to merge two linked lists
function merge(head1, head2) {
var merged = new Node(-1);
var temp = merged;
// While head1 is not null and head2
// is not null
while (head1 != null && head2 != null) {
if (head1.data < head2.data) {
temp.next = head1;
head1 = head1.next;
} else {
temp.next = head2;
head2 = head2.next;
}
temp = temp.next;
}
// While head1 is not null
while (head1 != null) {
temp.next = head1;
head1 = head1.next;
temp = temp.next;
}
// While head2 is not null
while (head2 != null) {
temp.next = head2;
head2 = head2.next;
temp = temp.next;
}
return merged.next;
}
// Find mid using The Tortoise and The Hare approach
function findMid(head) {
var slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Function to print list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver Code
var head = new Node(7);
var temp = head;
temp.next = new Node(10);
temp = temp.next;
temp.next = new Node(5);
temp = temp.next;
temp.next = new Node(20);
temp = temp.next;
temp.next = new Node(3);
temp = temp.next;
temp.next = new Node(2);
temp = temp.next;
// Apply merge Sort
head = mergeSort(head);
document.write("Sorted Linked List is: <br/>");
printList(head);
// This code contributed by gauravrajput1
</script>
Producción:
Sorted Linked List is: 2 3 5 7 10 20
Complejidad del tiempo : O(n*log n)
Complejidad espacial: O(log n)
¡Consulte el artículo completo sobre Merge Sort para listas vinculadas 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