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

# 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)
{
    //////在下面完成代码
    //即反转以head为头结点的单向链表
    //pivot为基点
    //定义三个指针分别代表小于区域的头结点，等于区域的头结点，大于区域的头结点
    list_node*lefthead=NULL,*midhead=NULL,*righthead=NULL,*leftend=NULL,*midend=NULL,*rightend=NULL;
    while(head){
        if(head->val<pivot){
            if(lefthead==NULL){
                lefthead=head;
                leftend=head;
            }
            else{
                leftend->next=head;
                leftend=leftend->next;
            }
        }
        else if(head->val==pivot){
            if(midhead==NULL){
                midhead=midend=head;
            }
            else{
                midend->next=head;
                midend=midend->next;
            }
        }
        else{
            if(righthead==NULL){
                righthead=rightend=head;
            }
            else{
                rightend->next=head;
                rightend=rightend->next;
            }
        }
        head=head->next;
    }
    if(leftend!=NULL){
        leftend->next=midhead;
        if(midend!=NULL)
            midend->next=righthead;
        else leftend->next=righthead;
    }
    if(midend!=NULL){
        midend->next=righthead;
    }
    rightend==NULL?rightend=NULL:rightend->next=NULL;
    list_node*newhead = lefthead==NULL?(midhead==NULL?righthead:midhead):lefthead;
    while(newhead){
        cout<<newhead->val<<" ";
        newhead=newhead->next;
    }
    return lefthead==NULL?(midhead==NULL?righthead:midhead):lefthead;
}


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