题目的主要信息：

• 给出一个长度为 n 的单链表和一个值 x
• 返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧
• 两个部分之内的节点之间与原来的链表要保持相对顺序不变
• 进阶要求：时间复杂度 $O(n)O(n)$ ， 空间复杂度 $O(1)O(1)$

方法一：两次遍历复制法

具体做法：

可以用一个新链表来复制原来的链表，复制之前先添加一个无用表头，后续返回的时候去掉即可。

第一次遍历原始链表，将小于x的节点按照顺序连接在新链表后面（这里是每个节点值创建一个新节点连接，而非连接原始的节点），然后第二次遍历原始链表按照一个次的方式将大于等于x的节点按照顺序连接。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* res = new ListNode(-1); //添加表头
        ListNode* p = head;
        ListNode* q = res;
        while(p != NULL){ //第一次遍历
            if(p->val < x){ //将小于x的节点按照顺序连在前面
                ListNode* temp = new ListNode(p->val);
                q->next = temp;
                q = q->next;
            }
            p = p->next;
        }
        p = head; //回到链表头
        while(p != NULL){ //第二次遍历
            if(p->val >= x){ //将大于等于x的节点按照顺序连在后面
                ListNode* temp = new ListNode(p->val);
                q->next = temp;
                q = q->next;
            }
            p = p->next;
        }
        return res->next; //返回去掉表头
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，两次遍历全部链表
• 空间复杂度：$O(n)O(n)$，创建了一个长度为$nn$的新链表

方法二：一次遍历法

具体做法：

可以准备两个表头，小值表头用于连接小于x的节点，大值节点用于连接大于等于x的节点，最后将大值节点表后接null，小值节点表后节点去掉表头的大值节点表，返回去掉小值头的部分即可。如下图所示：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(-1);
        ListNode* p = small; //记录两个表头
        ListNode* large = new ListNode(-1);
        ListNode* q = large; 
        while(head != NULL){
            if(head->val < x){ //小于x，被小值链表的指针指
                small->next = head;
                small = small->next;
            }else{ //否则被大值链表的指针指
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = NULL; 
        small->next = q->next; //去掉大值链表头
        return p->next; //去掉小值链表头
    }
};

复杂度分析：

• 时间复杂度: $O(n)O(n)$，其中$nn$是原链表的长度，对该链表进行了一次遍历
• 空间复杂度: $O(1)O(1)$