波波老师您好，晚上当我复习leetcode 86题 Partition List 官方给出的答案时，发现其思路为分别创建两个新的 Linked Lists，然后进行合并操作，但是官方答案说这样做的空间复杂度为O(1)，我认为这是不对的，因为他并没有直接在原链表上进行穿针引线等操作，而是开辟新空间进行存储，空间复杂度应该是O(n)。

所以请问是官方错了吗？多谢老师！

以下来自leetcode官网：

class Solution {
public ListNode partition(ListNode head, int x) {

    // before and after are the two pointers used to create the two list
    // before_head and after_head are used to save the heads of the two lists.
    // All of these are initialized with the dummy nodes created.
    ListNode before_head = new ListNode(0);
    ListNode before = before_head;
    ListNode after_head = new ListNode(0);
    ListNode after = after_head;

    while (head != null) {

        // If the original list node is lesser than the given x,
        // assign it to the before list.
        if (head.val < x) {
            before.next = head;
            before = before.next;
        } else {
            // If the original list node is greater or equal to the given x,
            // assign it to the after list.
            after.next = head;
            after = after.next;
        }

        // move ahead in the original list
        head = head.next;
    }

    // Last node of "after" list would also be ending node of the reformed list
    after.next = null;

    // Once all the nodes are correctly assigned to the two lists,
    // combine them to form a single list which would be returned.
    before.next = after_head.next;

    return before_head.next;
}

}

Complexity Analysis（复杂度解析）

Time Complexity: O(N), where N is the number of nodes in the original linked list and we iterate the original list. （时间复杂度为O(n)，我们遍历了原链表）

Space Complexity: O(1), we have not utilized any extra space, the point to note is that we are reforming the original list, by moving the original nodes, we have not used any extra space as such. （空间复杂度为O(1)，并没有开辟新空间）