使用优先队列对链表进行排序

Question

public class SortList{
   class ListNode{
      ListNode next;
      int val;

    public ListNode(int val){
      this.val = val;
     }
}   
public static ListNode sortList(ListNode head) {
    if(head == null)
        return null;
    PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>( (a,b) -> (a.val - b.val));
    while(head != null){
        pq.add(head);
        head = head.next;
    }
    ListNode pointer = pq.poll();
    ListNode result = pointer;
    while(pq.size() >0 ){
    System.out.println(pq.size());
        ListNode nextTemp = pq.poll();
        pointer.next = nextTemp;
        pointer = pointer.next;
    }
    return result;
}
  public static void main(String[] args){ 
  ListNode head = new ListNode(3);
  ListNode n2 = new ListNode(2);
  ListNode n3 = new ListNode(5);
  ListNode n4 = new ListNode(9);
  ListNode n5 = new ListNode(7);
  ListNode n6 = new ListNode(4);
  head.next = n2;
  n2.next = n3;
  n3.next = n4;
  n4.next = n5;
  n5.next = n6;
  n6.next = null;
  ListNode result = sortList(head);
   while(result != null){
   System.out.println(result.val);
   result = result.next;
    }
  }
 }

我想使用优先级队列对链表进行排序，但为什么在 poll() 直到队列为空时出现无限循环？列表大小减少但增加，优先级队列永远不会变空。

输出：

.........无限循环

Answer 1

让我们看看您的输出：

6
5
4
3
2
1  Up to this point, you're removing items from the priority queue
1  This is the first item in the sorted list output
2
3
4
6
7
9  End of the sorted list output
2  ?? This happens because 9 is pointing to 2 in the original list.
3
4
6
7
9

从您的输出中可以清楚地看出，您运行的代码与您发布的代码不同。我知道这是因为输出不包含值“5”，并且输出中有 7 个不同的项目，但代码中只有 6 个。

您的无限循环不在优先队列中。您可以通过修改 main() 来证明这一点，以便它在开始写入列表时输出一条消息，如下所示：

ListNode result = sortList(head);
System.out.println("Sorted list is:"); // start output
while(result != null){
    System.out.println(result.val);
    result = result.next;
}

正如我在评论中指出的那样，问题在于优先级队列中的最后一项具有非空 next 指针。所以当你删除它并将它添加到你的结果列表时，你最终会遇到一个循环。结果列表最终如下所示：

1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 9 ->
     ^                            \
      \                           /
       <-----<---------<--------<-

要解决此问题，请修改您的 sortList 方法，以便将列表中最后一项的 next 指针设置为 null:

while(pq.size() >0 ){
    System.out.println(pq.size());
    ListNode nextTemp = pq.poll();
    pointer.next = nextTemp;
    pointer = pointer.next;
}

pointer.next = null;  // terminate the list!!
return result;

这种错误很容易用调试器诊断出来。您可以单步执行代码以 确切地 查看它在做什么，并且您可以设置断点以便代码在特定行停止执行。如果您一直在使用调试器，您可能会在几分钟内发现这个问题。如果您不知道如何使用它，请学习。现在.

诊断这些问题的另一种方法是放置输出语句，如我所示。一个简单的 System.out.println("Finished the sort."); 会告诉您排序实际上已经完成，问题是稍后出现的。这是我们在拥有源代码级调试器之前使用的技术，今天对于调试服务、网页和其他在调试器中运行不方便的程序来说仍然非常方便。

使用优先队列对链表进行排序

Sort linked list using priority queue

java

algorithm

linked-list

priority-queue