ac

给定一个链表，再给定一个整数 pivot，请将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点， 右边部分都是大于 pivot 的节点。
除此之外，对调整后的节点顺序没有更多要求。

# 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)
{
    //////在下面完成代码, 不要求有序
    list_node *pHeadSmall = new list_node();
    list_node *pTailSmall = NULL;

    list_node *pHeadMid = new list_node();
    list_node *pTailMid = NULL;

    list_node *pHeadLarge = new list_node();

    list_node *p = head;
    while(p != NULL){
        list_node *pNext = p->next;

        if(p->val < pivot){
            if(pTailSmall == NULL){
                p->next = pHeadSmall->next;
                pHeadSmall->next = p;
                pTailSmall = p;
            }else{
                p->next = pHeadSmall->next;
                pHeadSmall->next = p;
            }
        }else if(p->val == pivot){
            if(pTailMid == NULL){
                p->next = pHeadMid->next;
                pHeadMid->next = p;
                pTailMid = p;
            }else{
                p->next = pHeadMid->next;
                pHeadMid->next = p;
            }
        }else{
            p->next = pHeadLarge->next;
            pHeadLarge->next = p;
        }
        p = pNext;
    }
    list_node *ans = NULL;
    if(pTailSmall != NULL){
        ans = pHeadSmall->next;
        if(pTailMid != NULL){
            pTailSmall->next = pHeadMid->next;
            pTailMid->next = pHeadLarge->next;
        }else{
            pTailSmall->next = pHeadLarge->next;
        }
    }else{
        if(pTailMid != NULL){
            ans = pHeadMid->next;
            pTailSmall->next = pHeadMid->next;
        }else{
            ans = pHeadLarge->next;
        }
    }
    p = ans;
    while(p != NULL){
        printf("%d ", p->val);
        p = p->next;
    }
    return ans;
}


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