Fusionner Trier une liste chaînée

Question

Je me suis récemment mis au travail sur certains principes de base et la fusion de la liste chaînée est un très bon défi. Si vous avez une bonne implémentation, montrez-le ici.

Answer 1

Je me demande pourquoi cela devrait être un gros défi, comme il est dit ici. Voici une implémentation simple en Java sans "astuces intelligentes".

 //The main function
public Node merge_sort(Node head) {
    if(head == null || head.next == null) { return head; }
    Node middle = getMiddle(head);      //get the middle of the list
    Node sHalf = middle.next; middle.next = null;   //split the list into two halfs

    return merge(merge_sort(head),merge_sort(sHalf));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public Node getMiddle(Node head) {
    if(head == null) { return head; }
    Node slow, fast; slow = fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}
 

Quelques explications supplémentaires ici - http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list

Answer 2

Plus simple/plus claire de la mise en œuvre pourrait être le récursive de la mise en œuvre, à partir de laquelle le NLog(N) le temps d'exécution est plus clair.

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
    // some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
    // Trivial case.
    if (!list || !list->next)
        return list;

    aList *right = list,
          *temp  = list,
          *last  = list,
          *result = 0,
          *next   = 0,
          *tail   = 0;

    // Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next)
    {
        last = right;
        right = right->next;
        temp = temp->next->next;
    }

    // Break the list in two. (prev pointers are broken here, but we fix later)
    last->next = 0;

    // Recurse on the two smaller lists:
    list = merge_sort_list_recursive(list, compare);
    right = merge_sort_list_recursive(right, compare);

    // Merge:
    while (list || right)
    {
        // Take from empty lists, or compare:
        if (!right) {
            next = list;
            list = list->next;
        } else if (!list) {
            next = right;
            right = right->next;
        } else if (compare(list, right) < 0) {
            next = list;
            list = list->next;
        } else {
            next = right;
            right = right->next;
        }
        if (!result) {
            result=next;
        } else {
            tail->next=next;
        }
        next->prev = tail;  // Optional.
        tail = next;
    }
    return result;
}

NB: Cela a un Log(N), les besoins de stockage de la récursion. Les performances devraient être à peu près comparable avec l'autre stratégie que j'ai posté. Il y a un potentiel d'optimisation ici par l'exécution de la fusion de la boucle while (list && droit), et simple en ajoutant le reste de la liste (puisque nous ne sommes pas vraiment à la fin de la liste; en sachant qu'ils sont fusionnés suffit).

Answer 3

Fortement basé sur le code EXCELLENT de: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Légèrement garni et rangé:

 
typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list;  // Trivial case

    do { // For each power of two<=list length
        numMerges=0,left=list;tail=list=0; // Start at the start

        while (left) { // Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
            // Cut list into two halves (but don't overrun)
            while (right && leftSize<listSize) leftSize++,right=right->next;
            // Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
                // Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
                // Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
                // Sort prev pointer
                next->prev=tail; // Optional.
                tail=next;          
            }
            // Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
        // Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
    return list;
}

 

NB: Ceci est garanti par O (NLog (N)) et utilise des ressources O (1) (pas de récursion, pas de pile, rien).

Answer 4

Une méthode intéressante consiste à conserver une pile et à ne fusionner que si la liste de la pile contient le même nombre d'éléments. Sinon, poussez la liste jusqu'à épuisement des éléments de la liste entrante, puis fusionnez la pile.

Answer 5

Le plus simple est de Gonnet + Baeza Yates Manuel d'Algorithmes. Vous l'appelez, avec le nombre d'éléments triés vous voulez, qui de manière récursive obtient traversée jusqu'à ce qu'il atteigne une demande pour une taille une liste qui vous puis il suffit de décoller le devant de la liste d'origine. Ces tous sont fusionnés en un grand liste triée.

[Notez que les frais de pile, l'un dans le premier post est appelé en Ligne de Mergesort et il obtient la moindre mention dans un exercice de Knuth Vol 3]