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