Partitionieren einer verketteten Liste um einen ganzzahligen Wert

Question

Ich versuche Code zu schreiben, um eine verkettete Liste um einen Wert x zu partitionieren, so dass alle Knoten kleiner als x vor allen Knoten größer oder gleich x kommen. Wenn x in der Liste enthalten ist, müssen die Werte von x nach den Elementen kleiner als x sein. Das Partitionselement x kann jedoch irgendwo in der "richtigen Partition" erscheinen.

Eingang 3-> 5-> 8-> 5-> 10-> 2-> 1 [Partition = 5] Ausgang 3-> 1-> 2-> 10-> 5-> 5-> 8

Die Knotenklasse ist wie folgt definiert.

class Node{ 
    Node next = null; 
    int data; 
    public Node(int d){ 
     data =d; 
    } 
    public Node() { 
     // TODO Auto-generated constructor stub 
    } 
    void appendToTail(int d){ 
     Node end = new Node(d); 
     Node n = this; 
     while(n.next!=null){ 
      n = n.next; 
     } 
     n.next = end; 
    } 

Unten ist ein halber Arbeitscode, den ich mir ausgedacht habe.

static void Partition(Node n,int numb){ 
    Node tail = n; 
    while(tail.next != null){ 
     tail = tail.next; 
    } 

Node current = n; 

Node tailCurrent = tail; 
Node prev = null; 
while(current!= tailCurrent){ 
    if(current.data<numb){ 

     prev = current; 
     System.out.println(prev.data); 
    } 
    else{ 
     prev.next = current.next; 
     tail.next = current; 
     tail = current; 

    } 
    current =current.next; 
} 


tail.next = null; 


} 

Es funktioniert für die Fälle, wo der feinen Kopfknoten eine ganze Zahl kleiner als die Unterteilungszahl hat jedoch tritt der Fehler auf, wenn der Kopf-Knoten eine ganze Zahl größer als oder gleich Partitionierungsnummer hat. Ich glaube, das liegt daran, dass in der else-Anweisung in meinem Code prev.next eine Nullzeiger-Ausnahme auslöst, weil sie niemals den if-Fall durchläuft, um einen Nicht-Null-Wert zu haben. Kann jemand vorschlagen, das zu beheben? Vielen Dank.

Answer 1

Wenn es keinen vorherigen Knoten zum Aktualisieren gibt, können Sie einfach nichts tun.

So dies ändern:

prev.next = current.next; 

dazu:

if (prev != null) { 
    prev.next = current.next; 
} 

Es gibt ein weiteres Problem: die Wurzel der Liste während der Partitionierung ändern kann, und es gibt keine Möglichkeit für den anrufenden Code zu Zugriff auf die neue Root erhalten. Es kann behoben werden, indem die Partition-Methode verfolgt, wo der aktuelle Stamm ist und es am Ende zurückgeben.

static Node Partition(Node n, int numb) { 
    Node tail = n; 
    while(tail.next != null) { 
     tail = tail.next; 
    } 
    Node current = n; 
    Node root = n; 
    Node tailCurrent = tail; 
    Node prev = null; 
    while(current != tailCurrent) { 
     if(current.data < numb) { 
      prev = current; 
     } else { 
      if (prev != null) { 
       prev.next = current.next; 
      } 
      if (root == current) { 
       root = current.next; 
      } 
      tail.next = current; 
      tail = current; 
     } 
     current = current.next; 
    } 
    tail.next = null; 
    return root; 
}