为什么返回一个带循环的列表？

Question

给定链表的头和值 x，对其进行分区，使得所有小于 x 的节点都位于大于或等于 x 的节点之前。 输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 示例2：

`输入：head = [2,1], x = 2 输出：[1,2]

Constraints:
The number of nodes in the list is in the range [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。但很可能在原始列表中它后面跟着一个值很小的节点，并且这个链接没有改变。

所以你需要将

great.next

设置为

null

并且

less.next

不应该设置为那个 tail 节点，而应该设置为第二个分区的 first 节点，即

greater.next

。

更正：

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