单链表-荷兰国旗问题

当下跟着B站视频学习算法——链表。视频中一开始就说笔试的时候，可以想到用数组来做，这样比较简单；如果面试的时候，就需要考虑“更好”的办法了，于是视频中娓娓道来。可是，作为链表，不是应该首先想到后者吗？！因为链表是很方便拆分合并的。

准备3个链表：左、中、右，分别存放小于、等于、大于的节点，然后把3个链表拼接起来就可以了。要实现这份代码，先实现链表的操作：判空，插入，拼接；然后是问题求解过程：遍历输入的链表，根据条件分别存入3个链表之一，最后把3个链表合并。

以下是代码：

typedef struct node {
    struct node *next;
    int value;
} node_t;


node_t* sort_list(node_t *list, int value);

typedef struct list {
    node_t *head, *tail;
} list_t;

static inline int
list_empty(list_t *list)
{
    return (!list->tail);
}

static inline void
list_init(list_t *list)
{
    list->head = list->tail = NULL;
}

static inline void
list_add(list_t *list, node_t *node)
{
    if (!list_empty(list)) {
        list->tail->next = node;
        list->tail = node;
    } else
        list->head = list->tail = node;
    node->next = NULL;
}

static inline void
list_join(list_t *dst, list_t *src)
{
    if (!list_empty(src))
        return;
    
    if (!list_empty(dst)) {
        dst->head = src->head;
        dst->tail = src->tail;
        list_init(src);
        return;
    }
    
    dst->tail->next = src->head;
    dst->tail = src->tail;
    list_init(src);
}

node_t*
sort_list(node_t *list, int value)
{
    list_t left, mid, right;
    list_init(&left);
    list_init(&mid);
    list_init(&right);
    
    while (node) {
        node_t *next = node->next;
        if (node->value < value)
            list_add(&left, node);
        else if (node->value == value)
            list_add(&mid, node);
        else
            list_add(&right, node);
        node = node->next;
    }
    
    list_join(&left, &mid);
    list_join(&left, &right);
    return (left.head);
}