程序员代码面试指南 2.8：将单链表按值划分

解法一：暴力

1、思路

把链表值全部复制到vector中，通过sort排序，然后遍历打印数值；
时间复杂度 $O (N)$ ，空间复杂度 $O (N)$ 。

2、代码

list_node * list_partition(list_node * head, int pivot)
{
    vector<int> v;
    auto p = head;
    
    while (p != nullptr)
    {
        v.push_back(p->val);
        p = p->next;
    }
    
    sort(v.begin(), v.end());
    
    for (int &i : v)
    {
        cout << i << " ";
    }
    
    return head;
}

解法二

1、思路

将链表分成三段，每段用两个指针来标记头尾，共需要6个指针;
遍历原链表，根据节点的值将其插入到对应的链表中，最后把三条链表合并成一条；
时间复杂度 $O (N)$ ，因为只使用了额外的6个指针，所以空间复杂度为 $O (1)$ 。

2、代码

list_node * list_partition(list_node * head, int pivot)
{
    // s : small, e : equal, b : big
    list_node *sH = nullptr, *sT = nullptr, *eH = nullptr, *eT = nullptr;
    list_node *bH = nullptr, *bT = nullptr, *next = nullptr;
    
    while (head != nullptr)         //步骤二
    {
        next = head->next;
        head->next = nullptr;
        
        if (head->val < pivot)
        {
            if (sH == nullptr)
            {
                sH = head;
                sT = head;
            }
            else
            {
                sT = sT->next = head;         
            }
        }
        else if (head->val == pivot)
        {
            if (eH == nullptr)
            {
                eH = head;
                eT = head;
            }
            else
            {
                eT = eT->next = head;
            }
        }
        else
        {
            if (bH == nullptr)
            {
                bH = head;
                bT = head;
            }
            else
            {
                bT = bT->next = head;
            }
        }
        
        head = next;
    }
    
    if (sT != nullptr)              //步骤三
    {
        sT->next = eH;
        eT = eT == nullptr ? sT : eT;
    }
    
    if (eT != nullptr)
    {
        eT->next = bH;
    }
    
    //找出链表头并打印，注意 sH 与 eH 链表可能为空
    auto newHead = sH != nullptr ? sH : eH != nullptr ? eH : bH; 
    while (newHead != nullptr)
    {
        cout << newHead->val << " ";
        newHead = newHead->next;
    }
    
    return head;
}