C语言数据结构-单向链表

头文件：link.h

#ifndef __LINK_H__
#define __LINK_H__

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

/*节点数据类型*/
typedef struct node
{
    DataType data;              //数据域
    struct node *pNext;         //指针域
}LinkNode;

/* 标签数据类型 */
typedef struct list
{
    LinkNode *pHead;           //链表头节点指针
    int cLen;                  //当前链表节点个数
}LinkList;

#endif

源文件：link.c

#include "link.h"

创建一个新节点：
LinkList *createLinkList()
{
    LinkList *pList = NULL;

    pList = malloc(sizeof(LinkList));
    if (NULL == pList)
    {
        perror("fail to malloc");
        return NULL;
    }
    pList->pHead = NULL;
    pList->cLen = 0;

    return pList;
}

头插：
int insertHeadLinkList(LinkList *pList, DataType data)
{
    LinkNode * pInsertNode = malloc(sizeof(LinkNode));
    if (NULL == pInsertNode)
    {
        perror("fail to malloc");
        return -1;
    }
    pInsertNode->data = data;

    pInsertNode->pNext = pList->pHead;
    pList->pHead = pInsertNode;
    pList->cLen++;

    return 0;
}

遍历：

void showLinkList(LinkList *pList)
{
    LinkNode *pTmpNode = pList->pHead;

    while (pTmpNode != NULL)
    {
        printf("%d ", pTmpNode->data);
        pTmpNode = pTmpNode->pNext;
    }
    printf("\n");

}

判空：

int isEmptyLinkList(LinkList *pList)
{
    return pList->cLen == 0;
}

尾插：
int insertTailLinkList(LinkList *pList, DataType data)
{
    LinkNode *pInsertNode = malloc(sizeof(LinkNode));
    if (NULL == pInsertNode)
    {
        perror("fail to malloc");
        return -1;
    }
    pInsertNode->data = data;
    pInsertNode->pNext = NULL;

    if (isEmptyLinkList(pList))
    {
        pList->pHead = pInsertNode;
    }
    else
    {
        LinkNode *pTmpNode = pList->pHead;
        while (pTmpNode->pNext != NULL)
        {
            pTmpNode = pTmpNode->pNext;
        }
        pTmpNode->pNext = pInsertNode;
    }
    pList->cLen++;

    return 0;
}

头删:

int deleteHeadLinkList(LinkList *pList)
{
    if (isEmptyLinkList(pList))
    {
        return 0;
    }

    LinkNode *pFreeNode = pList->pHead;
    pList->pHead = pFreeNode->pNext;
    free(pFreeNode);
    pList->cLen--;

    return 0;
}

尾删：

int deleteTailLinkList(LinkList *pList)
{
    if (isEmptyLinkList(pList))
    {
        return 0;
    }
    else if (1 == pList->cLen)
    {
        deleteHeadLinkList(pList);
    }
    else
    {
        LinkNode *pTmpNode = pList->pHead;
        while (pTmpNode->pNext->pNext != NULL)
        {
            pTmpNode = pTmpNode->pNext;
        }
        free(pTmpNode->pNext);
        pTmpNode->pNext = NULL;
        pList->cLen--;
    }

    return 0;
}

查找单链表的某个节点：

LinkNode *findLinkList(LinkList *pList, DataType findData)
{
    LinkNode *pTmpNode = pList->pHead;

    while (pTmpNode != NULL)
    {
        if (pTmpNode->data == findData)
        {
            return pTmpNode;
        }
        pTmpNode = pTmpNode->pNext;
    }

    return NULL;
}

单链表倒置：

int reverseLinkList(LinkList *pList, DataType oldData, DataType newData)
{
    LinkNode *pTmpNode = NULL;
    while ((pTmpNode = findLinkList(pList, oldData)) != NULL)
    {
        pTmpNode->data = newData;
    }
    
    return 0;
}

销毁链表：

void destroyLinkList(LinkList **ppList)
{
    while ((*ppList)->pHead != NULL)
    {
        deleteHeadLinkList(*ppList);
    }
    free(*ppList);
    *ppList = NULL;

}

查找中间节点：
LinkNode *findMidLinkNode(LinkList *pList)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pFast;

    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        if (NULL == pFast)
        {
            break;
        }
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
    }

    return pSlow;
}

查找最后一个节点：

LinkNode *findLastKNode(LinkList *pList, int K)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pFast;
    int i = 0;
    for (; i < K; i++)
    {
        pFast = pFast->pNext;
    }
    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
    }

    return pSlow;
}

删除某个节点：

int deletePointNode(LinkList *pList, DataType deleteData)
{
    LinkNode *pPreNode = pList->pHead;
    LinkNode *pFreeNode = pList->pHead;

    while (pFreeNode != NULL)
    {
        if (pFreeNode->data == deleteData)
        {
            if (pPreNode == pFreeNode)
            {
                pList->pHead = pFreeNode->pNext;
                free(pFreeNode);
                pPreNode = pList->pHead;
                pFreeNode = pList->pHead;
            }
            else
            {
                pPreNode->pNext = pFreeNode->pNext;
                free(pFreeNode);
                pFreeNode = pPreNode->pNext;
            }
            pList->cLen--;
        }
        else
        {
            pPreNode = pFreeNode;
            pFreeNode = pFreeNode->pNext;
        }
    }

    return 1;
}

单链表反转：

void invertLinkList(LinkList *pList)
{
    LinkNode *pTmpNode = pList->pHead;
    LinkNode *pInsertNode = NULL;
    
    pList->pHead = NULL;
    while (pTmpNode != NULL)
    {
        pInsertNode = pTmpNode;
        pTmpNode = pTmpNode->pNext;
        
        pInsertNode->pNext = pList->pHead;
        pList->pHead = pInsertNode;
    }
    
    return ;
}

链表排序：

void sortLinkList(LinkList *pList)
{
    //链表为空或只有一个节点不需要排序
    if (isEmptyLinkList(pList) || 1 == pList->cLen)
    {
        return ;
    }
    //保存第二个节点并且从第一个节点后断开
    LinkNode *pInsertNode = NULL;
    LinkNode *pTmpNode = pList->pHead->pNext;
    pList->pHead->pNext = NULL;

    while (pTmpNode != NULL)
    {
        //找到要插入的节点
        pInsertNode = pTmpNode;
        pTmpNode = pTmpNode->pNext;

        //判断是否需要头插
        if (pInsertNode->data < pList->pHead->data)
        {
            //头插
            pInsertNode->pNext = pList->pHead;
            pList->pHead = pInsertNode;
        }
        else
        {
            //寻找插入位置
            LinkNode *p = pList->pHead;
            while (p->pNext != NULL && p->pNext->data < pInsertNode->data)
            {
                p = p->pNext;
            }
            //节点插入
            pInsertNode->pNext = p->pNext;
            p->pNext = pInsertNode;
        }
    }
}

判断链表是否有环：

int isLoopLinkList(LinkList *pList)
{
    LinkNode *pFast = pList->pHead;
    LinkNode *pSlow = pList->pHead;

    while (pFast != NULL)
    {
        pFast = pFast->pNext;
        if (NULL == pFast)
        {
            return 0;
        }
        if (pSlow == pFast)
        {
            return 1;
        }
        pFast = pFast->pNext;
        pSlow = pSlow->pNext;
        if (pFast == pSlow)
        {
            return 1;
        }
    }
}
int main(int argc, const char *argv[])
{
    LinkList *pList = NULL;
    LinkNode *pTmpNode = NULL;

    pList = createLinkList();

//    insertHeadLinkList(pList, 1);
    insertHeadLinkList(pList, 2);
    insertHeadLinkList(pList, 3);
    insertHeadLinkList(pList, 4);

    insertTailLinkList(pList, 5);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);
    insertTailLinkList(pList, 3);

    showLinkList(pList);
#if 0
    deleteHeadLinkList(pList);

    deleteTailLinkList(pList);

    showLinkList(pList);

    pTmpNode = findLinkList(pList, 3);
    if (pTmpNode != NULL)
    {
        printf("find %d\n", pTmpNode->data);
    }
    else
    {
        printf("not find\n");
    }

    reverseLinkList(pList, 3, 10);
    showLinkList(pList);
#endif
    
    pTmpNode = findMidLinkNode(pList);
    printf("mid node = %d\n", pTmpNode->data);

    pTmpNode = findLastKNode(pList, 3);
    printf("last K node = %d\n", pTmpNode->data);
#if 0    
    deletePointNode(pList, 3);
    showLinkList(pList);
    
    invertLinkList(pList);
    showLinkList(pList);

    sortLinkList(pList);
    showLinkList(pList);

//    destroyLinkList(&pList);
#endif

    //构造环形链表
    pTmpNode = pList->pHead;
    while (pTmpNode->pNext != NULL)
    {
        pTmpNode = pTmpNode->pNext;
    }
    pTmpNode->pNext = pList->pHead->pNext->pNext->pNext->pNext;

    if (isLoopLinkList(pList))
    {
        printf("is loop link.\n");
    }
    else
    {
        printf("is not loop link.\n");
    }

    return 0;
}