单向链表几个比较重要的函数（包括插入、删除、反转等）

先是链表的定义

//单向链表的定义
struct SNode
{
    int elem;
    struct SNode* next;
};

 下面就是单向链表的插入、删除、反转、按个反转、计算共同子串长度、合并两个有序链表、判断该链表是否有环的函数，有些不太好笔头描述

//0失败    1成功

//在指定结点node的后面插入一个结点
int insert_after(struct SNode* node, int elem)
{
    assert(node != NULL);
    struct SNode* newnode = (struct SNode*)malloc(sizeof(struct SNode));//给新结点分配内存
    if(newnode == NULL)    //创建失败返回失败
        return 0;
    newnode->elem = elem;
    newnode->next = node->next;    //把node的next传给newnode
    node->next = newnode;          //让node的next指向newnode
    return 1;
}


//删除指定结点node的后面一个结点, *elem用于接收被删除的值,可以为空
int delete_after(struct SNode* node, int* elem)
{
    assert(node!=NULL);    //传入的结点为NULL不运行
    if(node->next == NULL) //node下一个结点为空
        return 0;        
    struct SNode* delnode = node->next; //让delnode记录要删除的结点
    if(elem != NULL)    //调用者需要返回删除的值记录
        *elem = delnode->elem;
    node->next = delnode->next; //让node的next指向del原来next的指向
    free(delnode);    //一定要记得释放内存！！！
    return 1;
}


//超级重点
//单向链表的反转
struct SNode* reverse(struct SNode* list)
{
    assert(list != NULL);
    
    //如果该列表只有一个头结点或只有一个结点    则无需逆序直接退出
    if(list->next==NULL || list->next->next==NULL)
        return list;
    struct SNode* prev = NULL;
    struct SNode* curr = list->next;
    struct SNode* next = NULL;
    while(curr != NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    list->next = prev;    //让头结点指向逆序过后的结点
    return list;
}


//根据count反转单向链表
//相当于把该链表分割成了count个为一组的数个单向链表，依次反转
struct SNode* reverse_count(struct SNode* list, size_t count)
{
    assert(list != NULL);
    if(list->next==NULL || list->next->next==NULL)
        return list;
    struct SNode* prev = NULL;
    struct SNode* curr = list->next;
    struct SNode* next = NULL;

    struct SNode* last = list;    //用于记录当前的“头结点”
    struct SNode* first = NULL;   //用于记录下一次的“头结点”，之后要让last指向他
    while(curr != NULL)
    {
        first = curr;   //反转前的第一个结点也就是反转后的最后一个结点
        prev = NULL;    //这一步不能忘，每次都相当于一个新的链表开始反转
        for(size_t i = 0; i<count && curr!=NULL; i++) //当最后一组个数不够count个时curr来 
                                                        到了最末尾，退出循环
        {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        last->next = prev;//让上一组的最后一个结点指向反转后的结点
        last = first;     //last获得新的“头结点”， 上一组反转后的最后一个结点作为下一组开始反        
                             转的“头结点”
    }
    return list;
}


//合并两个升序的单向链表为一个，l1和l2都是升序的，合并到l3中保持有序    不需要创建新的结点
void merage_list(struct SNode* l1, struct SNode* l2,struct SNode* l3)
{
    assert(l1!=NULL && l2!=NULL && l3!=NULL);
    struct SNode* node1 = l1->next;
    struct SNode* node2 = l2->next;
    struct SNode* curr = l3;
    while(curr != NULL)    //这样子增加了循环判断次数,括号里的条件也可以为
                           //(node1!=NULL && node2!=NULL),这样下面要在加一句
    {
        if(node1->elem < node2->elem)
        {
            curr->next = node1;
            curr = node1;
            node1 = node1->next;
        }
        else
        {
            curr->next = node2;
            curr = node2;
            node2 = node2->next;
        }
    }
    // curr->next = node1!=NULL ? node1 : node2;
    l1->next = NULL;
    l2->next = NULL;
}


//计算链表中结点的个数也就是长度
size_t size_list(struct SNode* list)
{
    assert(list != NULL);
    size_t len = 0;
    struct SNode* node = list->next;
    while(node != NULL)
    {
        len++;
        node = node->next;
    }
    return len;
}


//求两个链表的共同子串长度
size_t common_subsequence(struct SNode* l1, struct SNode* l2)
{
    assert(l1!=NULL && l2!=NULL);
    size_t len1 = size_list(l1);
    size_t len2 = size_list(l2);

    struct SNode* node1 = l1->next;
    struct SNode* node2 = l2->next;
    if(len1 > len2)    //先让两条链表处于同一起跑线，也就是让长的先走几步
    {
        while(len1 != len2)
        {
            len1--;
            node1 = node1->next;
        }
    }
    else if(len1 < len2)
    {
        while(len1 != len2)
        {
            len2--;
            node2 = node2->next;
        }
    }
    //这时len1和len2已经相等
    while(node1!=node2 && node1!=NULL && node2!=NULL)
    {
        len1--;    //每次循环长度-1，遇到相同的或者到达最后一个退出
        node1 = node1->next;
        node2 = node2->next;
    }
    return len1;    //剩下的就是共同字串长度，为0则说明没有子串
}


//判断链表是否有环    返回环的长度
size_t is_loop(struct SNode* list)
{
    assert(list != NULL);
    //让两个人一快一慢开始走路，若两个人碰到了一起则说明有环
    struct SNode* quick = list->next;
    struct SNode* slow = list->next;
    size_t len = 0;
    while(quick!=NULL && quick->next!=NULL) //因为quick一次走两步，所以要判断下quick的next
    {
        quick = quick->next->next;
        slow = slow->next;
        if(quick == slow)
        {
            //让慢的不动快的再走一圈计算环的长度
            do    //这里要记得使用do{}while();    因为quick和slow相同进入不了循环
            {
                quick = quick->next;
                len++;
            }while(quick != slow);
            return len;
        }
    }
    return 0;
}