一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为o(n)，不能申请新空间。

题意：给定一个单链表，以第一个元素为基准，将小于该元素的节点全部放到前面，大于该节点的元素全部放到后面。要求时间复杂度为O(n)，不能申请新空间。

解题思路：可以使用两个指针p, q，p指向小于该元素的最后一个节点，q指向当前遍历的节点。从头遍历链表，当遇到小于该元素的节点时，将其交换到p的后面，p和q都向后移动一位。如果遇到大于等于该元素的节点，q直接向后移动一位。最后，将第一个节点与p节点的值交换即可。

时间复杂度为O(n)，不需要申请新空间。

相关问题

设计算法，对于一个带头结点的整数单链表，以第1个结点为基准，将所有小于其值的结点移动到它的前面，将所有大于等于其值的结点移动到它的后面。

### 回答1：
1. 定义三个指针：pre指向小于基准值的最后一个结点（初始为头结点），cur指向当前遍历的结点，next指向cur的下一个结点。
2. 遍历整个链表，如果cur的值小于基准值，则将cur插入到pre之后，同时更新pre的位置；否则继续遍历。
3. 遍历完成后，将基准值结点插入到pre之后，链表就按照要求分成了两部分。

代码如下：

void partition(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return;
    int pivot = head->val;  // 基准值
    ListNode* pre = head;
    ListNode* cur = head->next;
    while (cur != nullptr) {
        ListNode* next = cur->next;
        if (cur->val < pivot) {
            cur->next = pre->next;
            pre->next = cur;
            pre = cur;
        } else {
            pre = pre->next;
        }
        cur = next;
    }
    // 将基准值插入到pre之后
    ListNode* pivot_node = new ListNode(pivot);
    pivot_node->next = pre->next;
    pre->next = pivot_node;
}

### 回答2：
设计算法如下：

1. 初始化三个指针，分别为smallerHead用于指向小于基准值的链表的头节点，smallerTail用于指向小于基准值的链表的尾节点，cur用于遍历链表。

2. 遍历链表，将小于基准值的节点移动到smaller链表中。具体操作如下：
- 如果cur指向的节点的值小于基准值：
* 如果smallerHead为空，则将smallerHead指向当前节点，smallerTail也指向当前节点。
* 如果smallerHead不为空，则将smallerTail的下一个节点设为当前节点，更新smallerTail指针。
- 移动cur指针到下一个节点。

3. 初始化两个指针，biggerHead用于指向大于等于基准值的链表的头节点，biggerTail用于指向大于等于基准值的链表的尾节点。

4. 继续遍历链表，将大于等于基准值的节点移动到bigger链表中。具体操作如下：
- 如果cur指向的节点的值大于等于基准值：
* 如果biggerHead为空，则将biggerHead指向当前节点，biggerTail也指向当前节点。
* 如果biggerHead不为空，则将biggerTail的下一个节点设为当前节点，更新biggerTail指针。
- 移动cur指针到下一个节点。

5. 将smallerTail和biggerHead连接起来，即将小于基准值的链表尾节点的下一个节点指向大于等于基准值的链表的头节点。

6. 如果smallerHead为空，则说明链表中没有小于基准值的节点，直接返回biggerHead作为排好序的链表的头节点；否则，返回smallerHead作为排好序的链表的头节点。

### 回答3：
设计算法如下：

1. 创建两个指针before和after，初始时都指向头结点。
2. 遍历链表，比较每个结点的值与基准值的大小关系：
a. 如果结点的值小于基准值，则将该结点移到前面，即将该结点的next指针指向before上一个结点，再将before指向该结点。
b. 如果结点的值大于等于基准值，则继续遍历下一个结点。
3. 遍历完毕后，将after指针指向最后一个小于基准值的结点的next指针，即所有大于等于基准值的结点跳过了。
4. 将before指针指向第一个结点的前一个结点，即头结点的前一个结点。
5. 如果存在小于基准值的结点，则before的next指针指向第一个小于基准值的结点；否则，before的next指针指向基准值结点。
6. 将基准值结点的next指针指向after即可完成整个链表的重新排列。

算法的时间复杂度为O(n)，其中n是链表的长度。

cpp，以单链表的首结点值， 为基准将该单链表分割为两 部分，使所有小于工的结点排在大于或等于x

的结点之前。

解题思路：

1. 定义两个指针分别指向小于x的链表和大于等于x的链表，初始化时都为空；
2. 遍历单链表，将小于x的结点插入到小于x的链表中，将大于等于x的结点插入到大于等于x的链表中；
3. 将小于x的链表尾部指向大于等于x的链表头部，即可完成分割操作。

参考代码：

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less = nullptr;   // 小于x的链表
        ListNode* greater = nullptr;    // 大于等于x的链表
        ListNode* lessTail = nullptr;   // 小于x的链表尾部指针
        ListNode* greaterHead = nullptr;    // 大于等于x的链表头部指针

        while (head != nullptr) {
            if (head->val < x) {
                if (less == nullptr) {
                    less = head;
                    lessTail = head;
                }
                else {
                    lessTail->next = head;
                    lessTail = head;
                }
            }
            else {
                if (greater == nullptr) {
                    greater = head;
                    greaterHead = head;
                }
                else {
                    greater->next = head;
                    greater = head;
                }
            }
            head = head->next;
        }

        if (less != nullptr) {
            lessTail->next = greaterHead;
            return less;
        }
        else {
            return greaterHead;
        }
    }
};

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(4);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(2);

    cout << "Original List: ";
    printList(head);

    Solution solution;
    ListNode* newHead = solution.partition(head, 3);

    cout << "After Partition: ";
    printList(newHead);

    return 0;
}

运行结果：

Original List: 1 4 3 2 5 2 
After Partition: 1 2 2 4 3 5