为什么在对链表进行分区时要进入无限循环

Question

这是将链表划分为两部分的常见问题。节点小于x的列表将位于第一位，节点大于x的列表位于第二位。

我的问题是，为什么在创建了两个单独的链表后，我需要将after.next设置为null？在不将其设置为null的情况下，我在尝试打印此列表时进入了一个无限循环。我的调试器显示before_head.next有一个没完没了的节点列表…

public Node partition(Node head, int x){
Node before_head=new Node(0);
Node before=before_head;
Node after_head=new Node(0);
Node after=after_head;
while(head != null){
if(head.val < x){
before.next=head;
before=before.next;
else{
after.next=head;
after=after.next;
}
head=head.next;
}
after.next=null;
before.next=after_head;
return before_head.next;
}

Answer 1

为什么在创建两个单独的链表后，我需要将after.next设置为null？

链表的最后一个节点没有下一个节点。在像您这样的链表表示中，它采用最后一个节点的next引用为null的形式。

您正在通过更改列表中现有节点的next引用来重新排列这些节点。在该过程结束时，after是对最后一个节点的引用，因此其next引用需要为null。如果它也是原始顺序中的最后一个节点，那么一切都很好——它的next引用已经为空。但是，如果after不是原始顺序中的最后一个节点，则after.next将引用其他节点之一，直到将其设置为null。无论其他节点是什么，它都以新的顺序出现在after之前，形成一个循环。

---

同时注意

before.next=after_head;

似乎是错误的。after_head是第二个分区的伪头节点，因此您不希望将其包含在新列表中。我想你想要

before.next = after_head.next;