Javaでリンクリストをソートする正しい方法は何ですか？

Question

私は、このリンクリストがあります：

class Node { 
    Node next; 
    int num; 

    public Node(int val) { 
     num = val; 
     next = null; 
    } 
} 

public class LinkedList { 

    Node head; 

    public LinkedList(int val) { 
     head = new Node(val); 
    } 

    public void append(int val) { 
     Node tmpNode = head; 
     while (tmpNode.next != null) { 
      tmpNode = tmpNode.next; 
     } 
     tmpNode.next = new Node(val); 
    } 
    public void print() { 
     Node tmpNode = head; 
     while (tmpNode != null) { 
      System.out.print(tmpNode.num + " -> "); 
      tmpNode = tmpNode.next; 
     } 
     System.out.print("null"); 
    } 

    public static void main(String[] args) { 
     LinkedList myList = new LinkedList(8); 
     myList.append(7); 
     myList.append(16); 
     myList.print(); 
    } 
} 

をし、私は、このリンクリストを並べ替える方法を知りたいですか？私はそれを並べ替えようとしましたが、奇妙な数字が出始めて、それ以外の場合は何もせず、何も並べ替えません。

Answer 1

リンクリストを挿入中に並べ替えることができます。あなたがそれをソートするために別の関数を必要としないように。先頭のシナリオを考慮しなかったのは、エラーが発生したヘッドだけがNULLになる場合です。

public void insert(int val) { 
Node currentNode = head; 
Node nextNode = head.next; 

if (head==null) { 
    head = new Node(val); 
    head.next = null; 
    return; 
} 

if (currentNode.num > val) { 
    Node tmpNode = head; 
    head = new Node(val); 
    head.next = tmpNode; 
    return; 
} 

if (nextNode != null && nextNode.num > val) { 
    currentNode.next = new Node(val); 
    currentNode.next.next = nextNode; 
    return; 
} 

while (nextNode != null && nextNode.num < val) { 
    currentNode = nextNode; 
    nextNode = nextNode.next; 
} 

currentNode.next = new Node(val); 
currentNode.next.next = nextNode; 
}