整数値を中心としたリンクリストの分割

Question

xより小さいすべてのノードがx以上のすべてのノードの前に来るように、値の周りにリンクリストを分割するコードを記述しようとしています。 xがリスト内に含まれている場合、xの値はxより小さい要素の後にある必要があります。ただし、パーティション要素xは、「正しいパーティション」のどこにでも置くことができます。

入力3→5→8→5→10→2→1 [パーティション= 5] 出力3→1→2→10→5→5→8

Nodeクラスは以下のように定義されています。

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

以下は、私が思い付いた半分の作業コードです。ヘッドノードは、以上分割数に等しい整数である場合

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; 


} 

それはヘッドノードが分割数よりも少ない整数を有する場合を正常に動作が、しかしエラーが発生します。これは、私のコードのelse文では、prev.nextがnullポインタ例外をスローするためです。なぜなら、nullでない値を持つif caseを決して通過しないからです。誰もがこれを修正する方法を提案することはできますか？ありがとうございました。

Answer 1

更新するノードがない場合は、何もしないでください。

ので、この変更：リストのルートは、パーティショニング時に変更される可能性があり、かつに呼び出し元のコードのための方法はありません：別の問題があり

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

：これまで

prev.next = current.next; 

を新しいルートにアクセスします。 Partitionメソッドで現在のルートがどこにあるかを追跡し、最後に戻すことで修正できます。

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