在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

您可以在插入自身时对链表进行排序。所以你不需要另外的函数来排序它。您没有考虑最初的情况，其中头部将仅为空，即错误是

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; 
}