Zählen Inversionen in einer verketteten Liste mit O (n log n) Laufzeit

Question

ich eine sehr einfache verknüpfte Liste in Java erstellt haben:

public class LinkedList { 
    class Node { 
     public Node next; 
     public int item; 

     public Node (int item) { 
      this.item = item; 
     } 
    } 

    int listSize = 0; 
    Node first = null; 
    Node last = null; 

    public void add(int n) { 
     Node node = new Node(n); 
     if (first == null) { 
      first = node; 
     } else { 
      last.next = node; 
     } 
     last = node; 
     listSize++; 
    } 
} 

So in der Hauptklasse, werde ich Hinzufügen von Elementen werden zu der verknüpften Liste in zufälliger Reihenfolge. Aber wie kann ich eine Methode erstellen, die die Anzahl der Inversionen in der Linked-List zählt?

Bisher habe ich es geschafft, es zu erreichen mit O (N^2) Laufzeit:

public int inversionCount() { 
     int count = 0; 
     Node current = this.first; 
     for (int i = 0; i <= this.listSize - 2; i++) { 
      Node next = current.next; 
      for (int j = i + 1; j < this.listSize; j++) { 
       if (current.item > next.item) { 
        System.out.print("(" + current.item + "," + next.item + ")" + " "); 
        count += 1; 
       } 
       next = next.next; 
      } 
      current = current.next; 
     } 
     return count; 
    } 

jedoch, wie gesagt, die Laufzeit für diesen Algorithmus ist O (N^2) . Ich versuche eine Laufzeit von O (NlogN) zu erreichen. Wie kann dies erreicht werden?

Answer 1

Sie Blase verwenden Sorte, die besitzt Komplexität O (n^2)

der Algorithmus zur verketteten Liste, die mit der Komplexität der O (n log n) anwendbar ist ist Merge Sort.

Bitte sehen this walk trough of merge sort for linked lists