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;
}
}
}
I want to sort a linked list using a priority queue, but why am I getting an infinite loop while poll() until queue is empty? The list size decreases but it increases, the priority queue never get empty.
Output:
6
5
4
3
2
1
1
2
3
4
6
7
9
2
3
4
6
7
9
2
3
4
6
7
9
2
3
4
6
7
9
2
3
4
6
......... infinite loop
Let's take a look at your output:
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
It's clear from your output that the code you ran is not the same as the code you posted. I know this because the output doesn't contain the value "5", and there are 7 distinct items in your output, but only 6 in your code.
Your infinite loop is not in the priority queue. You can prove this by modifying your main() so that it outputs a message when it starts writing the list, like this:
ListNode result = sortList(head);
System.out.println("Sorted list is:"); // start output
while(result != null){
System.out.println(result.val);
result = result.next;
}
The problem, as I pointed out in comments, is that the last item in the priority queue has a non-null next pointer. So when you remove it and add it to your result list, you end up with a loop. The result list ends up looking like this:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 9 ->
^ \
\ /
<-----<---------<--------<-
To fix this, modify your sortList method so that it sets the next pointer on the last item in the list to 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;
This kind of error is easy to diagnose with a debugger. You could single-step the code to see exactly what it's doing, and you can set breakpoints so the code will stop executing at specific lines. You could have found this problem in a matter of minutes had you been using your debugger. If you don't know how to use it, learn. Now.
The other way to diagnose these problems is by placing output statements, as I showed. A simple System.out.println("Finished the sort."); would have told you that the sort was in fact completing, and the problem was occurring later. This is the technique we used before we had the luxury of source level debuggers, and it's still very handy today for debugging services, web pages, and other programs that aren't convenient to run in a debugger.