Sortowanie LinkedList nawet po elementach nieparzystych

Question

Próbuję rozwiązać to pytanie: "Rozmieść elementy na danej liście połączonej tak, aby wszystkie liczby parzyste były umieszczone po liczbach nieparzystych. Odpowiednia kolejność elementów powinna pozostać taka sama."

Jest to kod używam:

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

Jest to główny logika:

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; 
} 

Zasadniczo mam manipulowane MergeSort algorytm trochę rozwiązać ten jeden, jeśli napotykają dziwne elementy, dodaję je najpierw w metodzie sortOddEvenMerger, a nawet elementy po nich. Ale względna kolejność elementów ulega zmianie.

Przykład: Wejście - 1 4 5 2

Przewidywana moc - 1 5 4 2

moje wyjście - 1 5 2 4

Jak mogę dostosować go więcej, aby utrzymać względna kolejność?

Answer 1

Twoje podejście nie tylko sprawia, że ​​problem jest trudniejszy niż jest, ale jest także bardziej nieefektywne, ponieważ jeśli dobrze rozumiem, to jest to O(nlgon). Dzieje się tak, ponieważ próbujesz wdrożyć algorytm mergesort i sortujesz dziwne (i równe) elementy, które prowadzą do złych wyników.

prosty algorytm:

• dokonać dwóch nowych list (jeden dla nieparzystych jeden dla parzystych elementów), które są początkowo puste.

• Przejrzyj główną listę i dodaj każdy nieparzysty element, który znajdziesz na liście parzystej i każdy element parzysty na liście parzystej. Jest to O(n) dla przejścia i O(1) dla każdego wstawienia w każdej liście.

• Gdy na liście głównej nie ma żadnych elementów, masz dwie listy nieparzyste - nawet z elementami o odpowiedniej kolejności, więc połącz je tak, aby uzyskać jedną listę z oczekiwanym wyjściem - ten krok to także O(1)!

Całkowita złożoność: O (n). (gdzie n długość głównej listy).