Trier LinkedList avec même après des éléments impairs

Question

J'essaie de résoudre cette question: "Disposer les éléments dans une liste liée donnée de telle sorte que tous les nombres pairs soient placés après les nombres impairs, l'ordre respectif des éléments doit rester le même."

C'est le code que je utilise:

class Node<T> { 
    T data; 
    Node<T> next; 
    Node(T data) { 
     this.data = data; 
    } 
} 

C'est la logique principale:

static Node<Integer> sortOddEven(Node<Integer> head) { 
    if(head == null || head.next == null) { 
     return head; 
    } 

    Node<Integer> middle = getMiddle(head); 
    Node<Integer> nextOfMiddle = middle.next; 

    middle.next = null; 

    Node<Integer> temp1 = sortOddEven(head); 
    Node<Integer> temp2 = sortOddEven(nextOfMiddle); 

    Node<Integer> sortedList = sortOddEvenMerger(temp1, temp2); 
    return sortedList; 
} 

static Node<Integer> sortOddEvenMerger(Node<Integer> head1, Node<Integer> head2) { 
    Node<Integer> head3 = null, tail3 = null; 

    if(head1.data.intValue()%2 != 0) { 
     head3 = head1; 
     tail3 = head1; 

     head1 = head1.next; 
    } else { 
     head3 = head2; 
     tail3 = head2; 

     head2 = head2.next; 
    } 

    while(head1 != null || head2 != null) { 

     if(head1 == null) { 
      tail3.next = head2; 

      return head3; 
     } else if(head2 == null){ 
      tail3.next = head1; 

      return head3; 
     } 

     if(head1.data.intValue()%2 != 0) { 
      tail3.next = head1; 
      tail3 = tail3.next; 

      head1 = head1.next; 
     } else { 
      tail3.next = head2; 
      tail3 = tail3.next; 

      head2 = head2.next; 
     } 

    } 

    tail3.next = null; 

    return head3; 
} 

En fait, je l'ai peaufiné MergeSort algorithme un peu pour résoudre celui-ci, si je rencontre étrange éléments, je les ajoute d'abord dans la méthode sortOddEvenMerger et même des éléments après eux. Mais l'ordre relatif des éléments est changé.

Exemple: entrée - 1 4 5 2

Résultats attendus - 1 5 4 2

Ma sortie - 1 5 2 4

Comment puis-je modifier plus à maintenir l'ordre relatif?

Answer 1

Votre approche non seulement rend le problème plus difficile qu'elle ne l'est mais est également plus inefficace puisque si je la comprends correctement, c'est O(nlgon). C'est parce que vous essayez d'implémenter l'algorithme de fusion et que vous triez les éléments impairs (et pairs) ce qui conduit à de mauvais résultats.

Un algorithme simple:

• Faire deux nouvelles listes (un pour un étrange même pour les éléments) qui sont vides. Traverse la liste principale et ajoute tous les éléments impairs que vous trouvez dans la liste impaire et tous les éléments pairs dans la liste paire. C'est O(n) pour traversal et O(1) pour chaque insertion dans chaque liste. Lorsque aucun élément n'est laissé dans la liste principale, vous avez deux listes impaires, même avec des éléments ayant un ordre correct, il suffit donc de les lier pour obtenir une liste avec la sortie attendue. Cette étape est également O(1)!

Complexité totale: O (n). (où n la longueur de la liste principale).