java - 单链表冒泡排序

Question

我已经在我的代码中实现了单链表，并且我必须对列表进行排序。 但我的代码不起作用，它陷入了无限循环。我必须根据节点的 id 按升序比较节点。

我不能使用数组。 这是我的 SLL 节点实现。

  class SLLNode implements Comparable<SLLNode> {
    protected int id;
    protected int plata;
    protected SLLNode succ;

    public SLLNode(int id,int plata, SLLNode succ) {
        this.id = id;
        this.plata=plata;
        this.succ = succ;
    }

    @Override
    public int compareTo(SLLNode o) {
        return o.id - this.id;
    }
}

public static void sort(SLL lista){
    SLLNode current;
    boolean check = true;
    while(check) {
        current = lista.getFirst();
        check = false;

        while(current.succ != null)
        {
            if(current.compareTo(current.succ) > 0)
            {
                SLLNode temp = current;
                current=current.succ;
                current.succ=temp;
                check = true;
            }
            current = current.succ;
        }
    }
}

Answer 1

您的问题在这里:

            // Take a copy of current.
            SLLNode temp = current;
            // Step to next.
            current=current.succ;
            // Point temp (old current) to new next <----- Added this.
            temp.succ = current.succ;
            // Point next's successor to current.
            current.succ=temp;
            // Remember to check again.
            check = true;

您缺少更改 temp.succ。您需要在适当的位置将其设置为 current.succ。

总之 - 要交换两个节点 a 和 b，您需要执行以下操作:

• 设置 a.succ = b.succ <--- 你错过了这个。
• 设置 b.succ = a

如果没有链接列表的示例实现，我无法测试它。