链表的分化问题

对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于这个值的结点移到前面，等于的值在中间，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。
本题最优的解法是：
遍历该链表，把其中小于/等于/大于的结点挂接在新的三个链表中，然后把这三个链表串接起来。因为没有new和delete操作，所以仅需很少的空间和时间开销。

不完整代码

ListNode* listDivide(ListNode* head, int val) {
//分别是三个链表的表头和表尾指针。表尾方便在尾部挂接结点。
        ListNode *h1=nullptr,*h2=nullptr,*h3=nullptr,*p1=nullptr,*p2=nullptr,*p3=nullptr;
        ListNode *p=head;
        while(p){
//遍历，每个结点找到属于它的三个链表中的一个，挂接到尾部。
            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;
}

以上的代码看似正常，其实是有问题的。问题在于拼合链表的时候，三个链表不一定每个都是有内容的。空指针的拼接往往会出错。
结合上述冗长的代码，可以把三个链表指针放在数组内进行遍历：利用一个belong函数，得到每个结点应该归属的链表，再进行操作。拼合的时候，利用一个变量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;
}