题解 | #将单向链表按某值划分为左边小，中间相等，右边大的形式#

思路：将链表划分为三个链表，最后再相连。注意相连的判断，如果中间没有，要直接连右边。

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

int pivot;

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d%d", &n, &pivot);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * list_partition(list_node * head, int pivot)
{
    //////在下面完成代码
    if(!head) return head;
    list_node * lefthead=nullptr,* midhead=nullptr,*righthead=nullptr,* left,*mid,*right,*temp=head;
    while(temp){
        if(temp->val<pivot){
            if(lefthead==nullptr){
                lefthead=temp;
                left=lefthead;
            }
            else{
                left->next=temp;
                left=left->next;
            }
        }
        else if(temp->val>pivot){
            if(righthead==nullptr){
                righthead=temp;
                right=righthead;
            }
            else{
                right->next=temp;
                right=right->next;
            }
        }
        else{
            if(midhead==nullptr){
                midhead=temp;
                mid=midhead;
            }
            else{
                mid->next=temp;
                mid=mid->next;
            }
        }
        temp=temp->next;
    }
    head=lefthead==nullptr?(midhead==nullptr?righthead:midhead):lefthead;
    if(lefthead!=nullptr){
        if(midhead!=nullptr) left->next=midhead;
        else left->next=righthead;
    }
    if(midhead!=nullptr) mid->next=righthead;
    if(righthead!=nullptr) right->next=nullptr;
    temp=head;
    while(temp){
        cout<<temp->val<<" ";
        temp=temp->next;
    }
    return head;
}


int main ()
{
    list_node * head = input_list();
    list_partition(head, pivot);
    return 0;
}