對于一個鏈表，我們需要用一個特定閾值完成對它的分化迅箩，使得小于這個值的結(jié)點移到前面，等于的值在中間拐揭，大于該值的結(jié)點在后面奕塑，同時保證兩類結(jié)點內(nèi)部的位置關(guān)系不變。
本題最優(yōu)的解法是：
遍歷該鏈表龄砰，把其中小于/等于/大于的結(jié)點掛接在新的三個鏈表中，然后把這三個鏈表串接起來。因為沒有new和delete操作值依，所以僅需很少的空間和時間開銷。

不完整代碼

ListNode* listDivide(ListNode* head, int val) {
//分別是三個鏈表的表頭和表尾指針颇蜡。表尾方便在尾部掛接結(jié)點辆亏。
        ListNode *h1=nullptr,*h2=nullptr,*h3=nullptr,*p1=nullptr,*p2=nullptr,*p3=nullptr;
        ListNode *p=head;
        while(p){
//遍歷，每個結(jié)點找到屬于它的三個鏈表中的一個缤弦，掛接到尾部彻磁。
            if(p->val<val){
//特別注意頭指針為空的情況狸捅。
                if(h1==nullptr){
                    h1=p;
                    p1=h1;
                }else{
                    p1->next=p;
                    p1=p1->next;
                }
            }else if(p->val==val){
                if(h2==nullptr){
                    h2=p;
                    p2=h2;
                }else{
                    p2->next=p;
                    p2=p2->next;
                }
            }else{
                if(h3==nullptr){
                    h3=p;
                    p3=h3;
                }else{
                    p3->next=p;
                    p3=p3->next;
                }
            }
            p=p->next;
        }
        //拼合三個鏈表
        p1->next=h2;
        p2->next=h3;
        p3->next=nullptr;//特別注意尾部的nullptr
        return h1;
}

以上的代碼看似正常累提，其實是有問題的。問題在于拼合鏈表的時候朽褪，三個鏈表不一定每個都是有內(nèi)容的无虚。空指針的拼接往往會出錯骑科。
結(jié)合上述冗長的代碼，可以把三個鏈表指針放在數(shù)組內(nèi)進行遍歷：利用一個belong函數(shù)梁棠，得到每個結(jié)點應(yīng)該歸屬的鏈表斗埂，再進行操作。拼合的時候呛凶，利用一個變量tail，只對不為空的鏈表進行拼接模闲。

int belong(const int a,const int b){
    if(a<b)
        return 0;
    if(a==b)
        return 1;
    if(a>b)
        return 2;
}
ListNode* listDivide(ListNode* head, int val) {
    ListNode *h[3]={};
    ListNode *t[3]={};
    ListNode *p=head;
    while(p){
        int pos=belong(p->val,val);
        if(h[pos]==nullptr){
            h[pos]=p;
            t[pos]=p;
        }else{
            t[pos]->next=p;
            t[pos]=p;
        }
        p=p->next;
    }
    head=nullptr;
    ListNode* tail=nullptr;
    for(int i=0;i<3;++i){
        if(h[i]){
            if(!head){
                head=h[i];
                tail=t[i];
            }else{
                tail->next=h[i];
                tail=t[i];
            }
        }
    }
    tail->next=nullptr;
    return head;
}