单链表

本文是单链表这种数据结构的总结。

不带头节点 与 带头节点

不带头节点的链表，在add/remove第一个节点时，需要改变链表入口指针的指向，而add/remove其他节点不需要，所以代码需要区别处理。

而额外加入一个不存储数据的节点，作为“头节点”，链表入口指针规定永远指向“头节点”，则在代码处理上不需要区分第一个节点与其它节点。

定义

typedef struct node{
    void        *data;
    struct node *next;
} node_t;                       // 节点类型

typedef node_t* slinked_list_t; // 单链表类型

初始化

int slinked_list_init( slinked_list_t *list )
{
    node_t *tmp = malloc(sizeof(node_t));
    if( tmp == NULL )
        return -1;
    *list = tmp;
    return 0;
}
// 初始化 参考代码
slinked_list_t task_list;
int ret = slinked_list_init( &task_list );
if( ret == -1 )
    perror("slinked list init error");

逆序遍历

• 尾指针法：用一个尾指针指到最后节点，从头节点走到尾节点，然后打印尾节点，尾节点前移，重复执行这一过程，直到头节点

• 记录法：顺序遍历单链表，记录到顺序数组中，然后再逆序遍历数组

• 递归法

void EndToFirstPrintSListNodeR(SListNode *ps)//递归打印
{
    if (NULL != ps->_next) //递归结束条件
        EndToFirstPrintSListNodeR(ps->_next);  //子问题
    printf("%d ",ps->_data);
}

• 逆序法：先逆序，然后再次 逆序 + 遍历

删除指定节点

删除最后一个节点时，只能遍历到它的前一个节点，然后删除它，复杂度为O(n)。

删除其他节点时，可以通过，将该节点的后一个节点next_node的数据，拷贝至当前节点cur，然后删除next_node,从结果上来看，就相当于删除了cur节点。复杂度O(1)。

所以均摊下来，函数整体复杂度为O(1)。

int slinked_list_remove( slinked_list_t list, node_t *cur )
{
    // cur is head node , error
    if( cur == list )
        return -1;

    // cur is final node
    if( cur -> next == NULL )
    {
        node_t *walk = list->next; // walk is first node now
        while( walk != NULL && walk->next != cur ){
            walk = walk->next;
        }
        walk->next = NULL;
        free(cur);
        return 0;
    }

    // cur is other node
    node_t *pre = cur;
    cur = cur -> next;      // cur is next node now
    pre->data = cur->data;
    pre->next = cur->next;
    free(cur);
    return 0;
}

在指定节点 前面 插入一个节点

把当前节点的数据域 “让给” 新插节点，而它自己则挪到新插节点，这就间接实现了 “前面” 插入。

int slinked_list_insert_before( slinked_list_t list, node_t *cur, void *data )
{
    // cur is head node
    if( cur == list )
        return -1;

    // new node
    node_t *tmp = malloc(sizeof(node_t));

    // move data of cur to new node
    tmp -> data = cur -> data;
    tmp -> next = cur -> next;

    // load added data to cur
    cur -> data = data;
    cur -> next = tmp;
    return 0;
}

约瑟夫环问题

// 约瑟夫环 entry: 环入口  num: 报数个数  keep_num: 保留人数
node_t *ysf_circle(node_t *entry, int num, int keep_num )
{
    node_t *cur = entry;
    cur = cur -> next;
    int cnt = 1;
    while( cur != entry )
    {
        cnt++;
        cur = cur -> next;
    }

    while( cur != cur -> next && cnt > keep_num )
    {
        int i = 1;
        while( i < num )
        {
            cur = cur -> next;
            i++;
        }
        node_t *rm = cur -> next;
        cur -> data = rm -> data;
        cur -> next = rm -> next;
        free(rm);
        cnt--;
    }

    return cur;
}