バブルソートを使用してリンクリストをソートすると、このコードが正しく動作しないのはなぜですか？

Question

以下のようにLinkedListを使用してバブルソートを実装しました。私はこの問題のための正確かつ効率的な解決策を見つけることができません。このコードでは、効率を上げるために必要な変更があります。誰かがリンクリストにバブルソートをより効率的に実装している場合は、それを提供してください。

class SortList { 
    int size; 
    Node head; 
    class Node{ 
    int data; 

    Node next; 
    Node(int data){ 
     this.data = data; 
     this.next = null; 
     } 
    Node(){ 
     this.data = 0; 
     this.next = null; 
    } 
    } 

    public void push(int d) { 
     Node newNode = new Node(); 

     newNode.data = d; 

     newNode.next = head; 

     head = newNode; 
     size++; 
    } 
    public void display(){ 
    Node n = head; 
    while(n!=null){ 
     System.out.print(n.data +" "); 

     n = n.next; 
     } 
    } 
    public int getLength(){ 
     int count=0; 
     Node n = head; 
     while(n!=null){ 
      count++; 
      n = n.next; 
      } 
      return count; 
    } 
    public int getLengthR(Node n){ 

      if(n==null) return 0; 
      return 1+getLengthR(n.next); 

    } 
    public int getL(){ 
    return getLengthR(head); 
    } 
    public static void main(String[] args) { 
     SortList ls = new SortList(); 
    int[]arrList = {5,2,7,3,1,2}; 
    for(int i=0;i<arrList.length;i++){ 
     ls.push(arrList[i]); 
     } 
     ls.display(); 

     ls.sortList(); 

     ls.display(); 
    } 

    public void sortList(){ 
    if(size > 1){ 
     Node node = head; 
     Node nextNode = head.next; 
      for(int i=0;i<size;i++){ 

      for(int j=0;j<size - i - 1;j++){ 
       while(node.data > nextNode.data){ 
        Node temp =node; 
        node = nextNode; 
        nextNode = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
     } 

     } 
    } 
} 

Answer 1

おそらくコメントで示唆されたStackOverFlowの回答を見てください。私はわずかに異なる戦術を使ってソート方法を変更しました。ノードを交換する代わりに、ノードの値を入れ替えました。あなたも交換することが必要になる場合がありますソートするために使用していないノードに関連付けられている他のデータがあるかもしれないので、これは常に、適用できないことがあります。

基本的に以下のアプローチは、各パスの後にいずれかによって、リストのサイズを小さくすることです。これは、変数terminalを使用して正しい位置に置かれたノードを追跡することによって行われます。

public void sortList(){ 
    if(size > 1){ 
     Node terminal = null; 
     while (head.next != terminal) { 
      Node node = head; 
      Node nextNode = head.next; 

      while (nextNode != terminal) { 
       if(node.data > nextNode.data){ 
        int temp =node.data; 
        node.data = nextNode.data; 
        nextNode.data = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
      terminal = node; 
     } 
    } 
}