为什么此代码无法正确使用冒泡排序对链表进行排序？

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

您或许应该看看评论中建议的 Whosebug 答案。我使用稍微不同的策略修改了您的排序方法。我没有交换节点，而是交换了节点中的值。这可能并不总是适用，因为可能还有其他数据与您未用于排序目的的节点关联，可能也需要交换这些数据。

基本上下面的方法是在每次通过后将列表的大小减一。这是通过使用变量 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;
        }
    }
}

为什么此代码无法正确使用冒泡排序对链表进行排序？

Why this code is not working correctly for sort a linkedlist using bubble sort?

java

sorting

linked-list

bubble-sort