Сортировка списка связанных списков

Question

Я хочу реализовать метод сортировки в моем пользовательском определенном Связанный список. Я пытаюсь реализовать использование пузырьковой сортировки, но не знаю, как это сделать.

class Node { 
    int data; 
    Node next; 

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

    public int getData() { 
     return data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setNext(Node next) { 
     this.next = next; 
    } 
} 

public class LinkedList { 
    private Node head; 

    public LinkedList() { 
     this.head = null; 
    } 

    public void insert(int data) { 
     Node node = new Node(data); 
     if (head == null) { 
      head = node; 
     } else { 
      Node temp = head; 

      while (temp.getNext() != null) { 
       temp = temp.getNext(); 
      } 
      temp.setNext(node); 
     } 
    } 

    public void reverse() { 
     Node temp = head; 
     Node back = null; 

     while (temp != null) { 
      Node next = temp.getNext(); 
      temp.setNext(back); 
      back = temp; 
      temp = next; 
     } 
     head = back; 
    } 

    public void print() { 
     Node temp = head; 
     while (temp != null) { 
      System.out.print(temp.getData() + " -- > "); 
      temp = temp.getNext(); 
     } 
    } 

    public void sort() { 
     // Bubble sort (but i am lost) 
     Node outer = head; 
     while(outer != null){   
      Node inner = head;   
      while(inner != null){ 
       // TODO 
      }   
      outer = outer.getNext(); 
     }  
    } 
} 

Answer 1

Вы должны начать с этого псевдо-кода, взятого из Wikipedia:

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat  
    swapped = false 
    for i = 1 to n-1 inclusive do 
     /* if this pair is out of order */ 
     if A[i-1] > A[i] then 
     /* swap them and remember something changed */ 
     swap(A[i-1], A[i]) 
     swapped = true 
     end if 
    end for 
    until not swapped 
end procedure 

Если вы можете поменять (я-1) -го и я-й элементы, вы должны быть в состоянии напишите все это (вы знаете, как просматривать связанный список).