为什么我的链表分区代码返回一个带有循环的列表？

Question

我正在解决LeetCode问题86。分区列表:

给定链表的头和值

x

，对其进行分区，使得所有小于

x

的节点都位于大于或等于到

x

的节点之前。

您应该保留两个分区中节点的原始相对顺序。

示例1：

输入：

head = [1,4,3,2,5,2], x = 3

输出：

[1,2,2,4,3,5]

示例2：

输入：

head = [2,1], x = 2

输出：

[1,2]

限制：

• 列表中的节点数量在

  [0, 200]

  范围内。

• -100 <= Node.val <= 100

• -200 <= x <= 200

我的代码：

    public static ListNode partition(ListNode head, int x) {
        ListNode lesser = new ListNode(-101);
        ListNode less = lesser;
        ListNode greater = new ListNode(-101);
        ListNode great = greater;
        ListNode temp= head;
        while(temp!=null){
            if(temp.val<x){
                less.next=temp;
                less=less.next;
            }
            else{
                great.next=temp;
                great=great.next;
            }
            temp=temp.next;
        }


        less.next = great.next;
        return lesser.next;
    }

我从测试中收到此错误：

错误 - 在 ListNode 中找到循环

谁能解释一下为什么会出现这个错误？

Answer 1

问题出在代码末尾：

循环结束后，

great

指向最后发现的值大于（或等于）主元的节点。因此，它应该成为最终列表的tail。但很可能在原始列表中它后面跟着一个值很小的节点，并且这个链接没有改变。

例如，对于输入示例

2→1

和 𝑥=2，我们在循环开始之前得到这种情况：

lesser less
   ↓     ↓
┌───────────┐
│ val: -101 │
│ next: null│
└───────────┘                    
                                 
greater great      head  temp
   ↓      ↓         ↓     ↓
┌───────────┐     ┌───────────┐     ┌───────────┐
│ val: -101 │     │ val: 2    │     │ val: 1    │
│ next: null│     │ next: ─────────►│ next: null│
└───────────┘     └───────────┘     └───────────┘

第一次迭代后：

lesser less
   ↓     ↓
┌───────────┐
│ val: -101 │
│ next: null│
└───────────┘                    
                                 
greater            head great        temp
   ↓                 ↓    ↓            ↓
┌───────────┐     ┌───────────┐     ┌───────────┐
│ val: -101 │     │ val: 2    │     │ val: 1    │
│ next: ─────────►│ next: ─────────►│ next: null│
└───────────┘     └───────────┘     └───────────┘

第二次迭代后：

lesser
   ↓
┌───────────┐
│ val: -101 │
│ next: ────────────────────────┐
└───────────┘                   │ 
                                │ 
greater            head great   │     less       temp==null
   ↓                 ↓    ↓     │       ↓
┌───────────┐     ┌───────────┐ │   ┌───────────┐
│ val: -101 │     │ val: 2    │ └──►│ val: 1    │
│ next: ─────────►│ next: ─────────►│ next: null│
└───────────┘     └───────────┘     └───────────┘

现在错误的语句

less.next = great.next

将引入循环——值为1的节点获得自引用！

首先，认识到

less

是第一个分区的最后一个节点，

great

是第二个分区的最后一个节点。这意味着

great.next

应该设置为

null

——它确实必须是最终列表中的最后一个节点。

其次，

less.next

确实应该更新，但应该设置为第二个分区的first节点，即

greater.next

（不是

great.next

）。

更正：

        great.next = null; // added
        less.next = greater.next; // corrected

在这两条语句之后，示例将解析为：

lesser
   ↓
┌───────────┐
│ val: -101 │
│ next: ────────────────────────┐
└───────────┘                   │ 
                                │ 
greater            head great   │     less       temp==null
   ↓                 ↓    ↓     │       ↓
┌───────────┐     ┌───────────┐ │   ┌───────────┐
│ val: -101 │     │ val: 2    │ └──►│ val: 1    │
│ next: ─────────►│ next:null │     │ next: ─┐  │
└───────────┘  ┌─►└───────────┘     └────────│──┘
               └─────────────────────────────┘

当我们返回

lesser.next

（正确）时，局部变量超出范围，上面简化为：

                                     (returned)     
                                        ↓
                  ┌───────────┐     ┌───────────┐
                  │ val: 2    │     │ val: 1    │
               ┌─►│ next:null │     │ next: ─┐  │
               │  └───────────┘     └────────│──┘
               └─────────────────────────────┘