为什么在分割链表时需要断开两个链表节点之间的链接？

Question

我试图解决LeetCode上Partition List问题。该问题要求在给定目标列表节点的情况下对链接列表进行排序，使所有小于目标值的列表节点出现在目标值之前，而它们的原始相对顺序保持不变。

我想出了一个简单的算法并通过了在线测试，基本上创建了两个指针并在遍历列表时使用它们来连接<目标或>=目标的节点。

public ListNode partition(ListNode head, int x) {
    ListNode ptr = head;
    ListNode small = new ListNode(0);
    ListNode big = new ListNode(0);
    ListNode dummy_1 = big;
    ListNode dummy_2 = small;
    int i = 1;
    while (ptr != null) {
        if (ptr.val < x) {
          small.next = ptr;
          small = small.next;
        } else {
          big.next = ptr;
          big = big.next;
        }
        ListNode help = ptr.next;
        ptr.next = null;
        ptr = help;
    }
    small.next = dummy_1.next;
    return dummy_2.next;
}

以下代码断开了ptr和ptr.next之间的链接，并将ptr移动到原始的ptr.next。

ListNode help = ptr.next;
ptr.next = null;
ptr = help;

我还没有完全弄清楚为什么需要这一步，因为我们可以将ptr移动到其next，然后在while循环中直接使用small.next = ptr和big.next = ptr更新引用；

然而，当我只使用ptr = ptr.next而不是以上三行代码时，在线评测机会出现Memory Limit Exceeded的错误。

如果有人能解释一下这是什么原因，我会非常感激。是否已经避免了任何循环列表，可能会导致内存限制错误？

- GettingBetter

---

你是用Java还是C++写这个代码？你的代码是C++，但你的标签是Java。 - JavaHopper

然而，这3行代码是必需的来回收内存。如果你只是移动指针，节点并没有被删除，指针只是指向链表中的下一个节点。 - JavaHopper

我已经在我的回答中解释了其中的区别。如果还不清楚，请告诉我。如果您理解背后的哲学，您可以接受/点赞这个答案。 - JavaHopper

@rcgldr 非常感谢！我再次研究了一下算法，认为这就是答案。如果列表以“小”节点结尾，则将其指向大列表的头部将会创建一个循环列表，因为大列表中的最后一个节点从未指向null。再次感谢！ - GettingBetter

@GettingBetter - 你可以使用ptr = ptr.next，然后在small.next = dummy1.next之后，设置big.next = null。我测试过了并发布了答案。 - rcgldr

Answer 1

如果一个对象被至少一个引用指向，它就不会成为垃圾回收的候选对象。您可以阅读this文章来对这个概念有一个简要的了解。

以下是两种情况下发生的情况： 情况1：

ptr = ptr.next

假设在第一次迭代期间，链表处于以下状态。

ptr 被推进了，但是前一个值为7的节点仍然被head引用。

ptr 被推进了，但是前一个节点的值为1仍被其前一个节点引用。

ptr被推进了，但是前一个具有值为3的节点仍然被其前一个节点引用。

直到循环结束，它才会停止。如果列表非常大，则不会回收内存。就像你的评委说的那样，这将导致错误，例如 Memory Limit Exceeded。 情况2：

    ListNode help = ptr.next;
    ptr.next = null;
    ptr = help;

假设在第一次迭代期间，链表处于以下状态。

• help 指向 ptr 所指的下一个节点
• ptr 被重新引用以指向 help，在下一步中
• 因此，先前由 ptr 指向的节点（其值为 7）有资格进行垃圾回收
• 并且内存被回收

• help 指向 ptr 指向的下一个节点
• ptr 在下一步被重新引用以指向 help
• 因此，之前由 ptr 指向的节点（具有值为1的节点）可以进行垃圾回收
• 并且内存被回收

• help 指向 ptr 指向的下一个节点
• ptr 在下一步中被重新引用以指向 help
• 因此，之前由 ptr 指向的节点（值为3的节点）符合垃圾回收条件
• 并且内存被回收

• help 指向 ptr 所指向的下一个节点
• ptr 在下一步中被重新引用以指向 help
• 因此，先前由 ptr 指向的节点（其值为 2 的节点）符合垃圾回收条件
• 并且内存得到回收

- JavaHopper

---

感谢您的详细解释，@JavaHopper！这真的帮助我理解内存处理。我还有一个问题，在断开ptr和ptr.next之前，在while循环中我们实际上已经让simple.next/big.net指向了ptr所指向的节点。由于该节点仍然有一个引用指向它，因此内存不会被回收，对吗？那么这与移动ptr而不进行断开有何不同呢？ - GettingBetter

正如您所看到的，如果在不断开链的情况下移动指针，则各个节点仍然彼此连接，因此在每次迭代后不会被垃圾回收。 - JavaHopper

Answer 2

正如评论所述，仅设置big.next = null即可运行（我使用netbeans / java运行了此操作）。

static ListNode partition(ListNode head, int x) {
    ListNode ptr = head;
    ListNode small = new ListNode(0);
    ListNode big = new ListNode(0);
    ListNode dummy_1 = big;
    ListNode dummy_2 = small;
    while (ptr != null) {
        if (ptr.val < x) {
          small.next = ptr;
          small = small.next;
        } else {
          big.next = ptr;
          big = big.next;
        }
        ptr = ptr.next;
    }
    small.next = dummy_1.next;
    big.next = null;
    return dummy_2.next;
}

- rcgldr