如何在两个节点之间交换数据?(Java)

Question

我一直在使用Nodes进行一个项目，对于这个项目，我们必须根据Nodes中的项所拥有的优先级(0-2，0是最高的，2是最低的(对Nodes进行排序(按降序(。现在我已经部分实现了这一点，因为当它真正进行交换时，它会将两个项目变成相同的(我只是想交换项目(。例如：我会输入Node_1，它持有0的prio，然后输入Node_2，它持有1的prio。然后它应该被排序为：

Node_2(holds prio 1) --> Node_1(holds prio 0)

那么它应该运行该方法，将它们排序为(优先级递减(：

Node_1(holds prio 0) --> Node_2(holds prio 1)

但相反，它只是将两个节点变成相同的(相同的优先级(：

Node_1(holds prio 0) --> Node_1(holds prio 0)

无论我添加多少节点，它都保持不变。它们都会转到优先级最高的同一个节点。任何帮助都会很棒。

代码：

private void sortJobs() {
Node p, q, r;
p = jobs;
q = null;
r = null;
//only runs if there is more than 1 job
while (p != null && p.next != null) {
q = p;
p = p.next;
if (q.item.getPriority() > p.item.getPriority()) {
r = q;
q.item = p.item;
p.item = r.item;

}
}
}

请告诉我是否有更好的方法来做这件事，因为我还在学习。

Answer 1

这已经在Andreas的回答中说过了，但我将进一步阐述。由于这是Java，所以您的temp(在本例中为r(只引用了q。这就是为什么当您更改writeq = p;时，r也会完全更改。因为它们引用了对象的同一实例。您需要创建一个临时项目才能正确交换。正确的解决方案是将r设置为项对象，然后设置p.item = r。希望这能有所帮助。

Answer 2

可能更像这样的东西：

private void sortJobs(Node p) {
if (p != null && p.next != null) {
Node q = p.next;
Item pItem = p.getItem();
Item qItem = q.getItem();
// check for nulls???  Safety???
if (qItem.getPriority() < pItem.getPriority()) {
p.setItem(qItem);
q.setItem(pItem);
}
// almost forgot the recursion
sortJobs(q);
}
}

可以按相同的顺序保留节点，但可以交换其中的项目。我们不需要复制到第三个伪值技巧中，因为我们已经有了对这两个项的引用(我们无论如何都需要引用来获取优先级(。

Answer 3

是否可以使用PriorityQueue而不是实现排序功能？

PriorityQueue<Node> pq = new PriorityQueue(new Comparator<Node>(){
public int compare(Node a, Node b){
return a.item.getPriority()-b.item.getPriority();
}
});
p=jobs;
if(p==null) return p;
//add all jobs in PriorityQueue
while (p != null) {
pq.add(p);
p=p.next;
}
//Change next pointer
Node head=pq.poll();
Node prev=head;
while(pq.size()>0){
Node n = pq.poll;
prev.next=n;
prev=n;
}
return head;