单链表冒泡排序

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

如果没有您的链接列表的示例实现，我无法对此进行测试。

Answer 2

节点*sorted_list(节点*头) {

node *index1,*index2;
enter code here
for(index1=head;index1->next!=NULL;index1=index1->next)
{
for(index2=index1->next;index2!=NULL;index2=index2->next) 
{
if(index1->data>index2->data) 
{
int temp=index1->data;
index1->data=index2->data;
index2->data=temp;
}
}
}
return head;

}

单链表冒泡排序

Singly Linked List bubble sort

java

linked-list

bubble-sort

singly-linked-list