LinkedListを並べ替える

Question

私はリンクされたリストを並べ替えることに問題があります。誰でも助けてくれて、間違っていることを教えてください。 私はソートしてリストに入れる必要があります。 と私に最後の新しいメソッドを使用してリストを印刷するためのいくつかのポインタを与えることができる場合は、public void print（）。

public class SortedLinkedList<T extends Comparable<? super T>> 
      extends LinkedList<T> 
    { 
     private LinkedList<T> list; //the sorted list 

     //the constructor 
     public SortedLinkedList(LinkedList<T> in) 
     { 
      if(in.isEmpty()) 
      { 
       System.out.println("Empty list"); 
      } 
      else 
      { 
       LinkedList<T> first = new LinkedList<T>(in.subList(0, in.size()/2)); 
       LinkedList<T> second = new LinkedList<T>(in.subList(in.size ()/2,in.size())); 
       LinkedList<T> sortList = new LinkedList<T>(); 

       int i = 0; 
       int j = 0; 
       while(i<first.size() && j<second.size()) 
       { 
        if(first.get(i).equals(second.get(j)) || first.get(i).compareTo(second.get(j))<0) 
        { 
          sortList.add(first.get(i)); 
          i++; 
        } 
        else 
        { 
          sortList.add(second.get(j)); 
          j++; 
        } 
        if(i == first.size()) 
        { 
          for(int k = j; k<second.size(); k++) 
          { 
           sortList.add(second.get(k)); 
          } 
        } 
        else 
        { 
          for(int x = i; x<first.size(); x++) 
          { 
           sortList.add(first.get(x)); 
        } 
       } 

      } 
     } 
    } 
    } 

Answer 1

あなた自身のソートを書く前に、Collections.sortを試してください。独自のソート順が必要な場合は、コンパレータを使用します。

いくつかの追加：ほとんどの場合、LinkedListsは間違ったデータ構造です。特に並べ替えが必要な場合は特にそうです。

Answer 2

Mergesortを実装しようとしているようです。私の前提が正しければ、あなたはサブリストのmergesortを再帰的に呼び出すことを忘れています。ラフアルゴリズムは、擬似コードでは、次のようになります。

mergesort(list) 
    left = list[:len(list/2)] 
    right = list[len(list/2):] 

    mergesort(left) 
    mergesort(right) 

    merge(left, right) # that would be your while loop 

編集：あなたが本当にあなた自身のアルゴリズムを実装する必要がない限り、私は、Java APIから、Collections.sortを使用することをお勧め。