特定のデータを持つリストにノードを挿入し、そのリストをJavaでソートする方法

Question

ソートしたままリンクリストに100を追加するにはどうすればよいですか？私は、単一リンクリストの先頭にアイテムを追加し、リストの最初のノードを指し示さなければならないことを知っていますが、この問題を解決する方法を見つけるのには非常に問題があります。

 IntegerNode n3 = new IntegerNode(9, null); 
     IntegerNode n2 = new IntegerNode(5, n3); 
     IntegerNode head = new IntegerNode(1, n2); 

     IntegerNode curr; 
     IntegerNode prev; 

     //print all the items in the linked-list 
     for(curr = head; curr!=null; curr = curr.getNext()) { 
      System.out.println(curr.getItem()); 
     } 

     int data = 100; 

     //insert an node to the list with the given data, and maintain the list to be sorted 
    } 
} 

Answer 1

以下insert方法は、開始すべきである：

1. をヘッドがnullの場合、現在の値を持つノードを作成し、それを設定：

   public void insert(int val){ 
       if(this.head==null){ //empty 
        this.head = new IntegerNode (val); 
        this.head.setNext(null); 
        return; 
       } 
       IntegerNode prev = null; 
       IntegerNode curr = this.head; 
       IntegerNode newNode = new SLLNode(val); 
       while(curr!=null && curr.getVal()<val){ 
        prev = curr; 
        curr = curr.getNext(); 
       } 
       if(prev==null){//new element to be placed at first 
        newNode.setNext(curr); 
        this.head = newNode; 
       } 
       else if(curr==null){// new element to be placed at end 
        newNode.setNext(null); 
        prev.setNext(newNode); 
       }else{ //intermediate position 
        newNode.setNext(curr); 
        prev.setNext(newNode); 
       } 
   } 
   

   手順は以下の通りです。ルートとして

2. Elseは、現在のノードよりも小さい値を持つ最大のノードを見つけるためにリストを反復処理します。このノードの前のノードと次のノードへの参照を保持します。
3. prevがnullの場合、挿入する値は現在リストにあるすべての値よりも小さく、最初に配置する必要があります。
4. currがnullの場合、これはリストの最後に到達したことを意味し、値は現在リスト内にあるすべてのノードよりも大きいので、最後にノードを設定します。

は、この情報がお役に立てば幸いです。