如何使用priority queue实现linked list排序及对应入队方法编写

现有代码问题 #

现有代码完全无法实现排序效果，核心原因有两点：

• 语法逻辑存在缺陷：if (isEmpty()) 分支后没有加else判断，后续尾插逻辑被放在独立代码块中，无论队列是否为空都会执行一次尾插，空队列场景下甚至会插入两个重复的新节点
• 缺少优先级匹配逻辑：所有新元素都直接追加到链表尾部，完全没有按照优先级大小匹配对应插入位置，仅能实现普通队列的FIFO效果

修复思路 #

默认以元素值升序作为优先级规则（值越小优先级越高，排列越靠前），可根据实际需求调整比较逻辑，入队执行步骤如下：

• 初始化待插入的新节点
• 队列为空时直接将首尾指针指向新节点，结束操作
• 若新元素优先级高于队首元素，直接插入到队首位置，更新队首指针
• 否则从队首开始遍历链表，找到第一个优先级低于新元素的节点，将新节点插入到该节点之前
• 若遍历到队尾都未找到符合条件的节点，说明新元素优先级最低，直接追加到队尾并更新队尾指针

修复后代码 #

@Override
public void priorityEnqueue(AnyType x) {
    ListNode<AnyType> newNode = new ListNode<>(x);
    // 空队列直接赋值首尾指针
    if (isEmpty()) {
        front = back = newNode;
        return;
    }
    // 新元素优先级高于队首，插在队头
    // 调整compareTo的比较符号即可修改排序规则，比如改为>就是按降序排列
    if (((Comparable<AnyType>) x).compareTo(front.data) < 0) {
        newNode.next = front;
        front = newNode;
        return;
    }
    // 遍历找到插入位置
    ListNode<AnyType> current = front;
    while (current.next != null && ((Comparable<AnyType>) x).compareTo(current.next.data) >= 0) {
        current = current.next;
    }
    // 插入新节点
    newNode.next = current.next;
    current.next = newNode;
    // 插入位置为队尾时更新尾指针
    if (current == back) {
        back = newNode;
    }
}

注意事项 #

如果你的AnyType泛型没有默认实现Comparable接口，可自行传入自定义比较器替换代码中的compareTo逻辑即可。

内容的提问来源于stack exchange，提问作者Kevin