目录

结构体

创建链表

插入链表

头插法

尾插法

遍历打印

更新链表指定节点

查找链表指定节点

删除链表指定节点

销毁链表

找到元素中间位置

 找到链表倒数第k个节点

链表元素倒置

链表元素排序

冒泡排序

选择排序

---

链表
    1.空间可以不连续，访问元素不方便
    2.链表需要更大的空间存放数据和节点地址
    3.链表空间不连续,使得理论上长度是无限的
    4.链表的插入和删除效率很高

结构体

typedef int DataType;
typedef struct node
{DataType data;struct node *pnext;
}LinkNode;

创建链表

LinkNode *CreateLinklist()
{LinkNode *pHead=NULL;pHead=malloc(sizeof(LinkNode));if(pHead==NULL){return NULL;}pHead->pnext=NULL;return pHead;
}

插入链表

头插法

int HeadInsertLink(LinkNode *pHead,DataType data)
{LinkNode *pTmpnode=NULL;
//申请一个新的节点空间pTmpnode=malloc(sizeof(LinkNode));if(pTmpnode==NULL){return -1;}
//为节点data赋值pTmpnode->data=data;
//新节点的pnext指向头结点的pnextpTmpnode->pnext=pHead->pnext;
//头结点的pnext指向新节点pHead->pnext=pTmpnode;return 0;
}

尾插法

int TailInsertLinkList(LinkNode *pHead, DataType TmpData)
{LinkNode *ptmpnode=NULL;LinkNode *Newnode=NULL;ptmpnode=pHead;
//找到最后一个节点(最后一个节点的特点是pnext为空)while (ptmpnode->pnext!=NULL){ptmpnode=ptmpnode->pnext;}
//申请一个新的节点空间Newnode=malloc(sizeof(LinkNode));if(Newnode==NULL){return -1;}
//为节点数据空间赋值Newnode->data=TmpData;
//新节点的pnext指向NULLNewnode->pnext=NULL;
//最后一个节点next指向当前节点,当前节点变为最后一个节点ptmpnode->pnext=Newnode;return 0;
}

遍历打印

int Showlist(void *Element,void *arg)
{int *data = Element;printf("%d  ",*data);return 0;
}
int ShowLinkList(LinkNode *pHead,int (*pFun)(void *Element,void *arg),void *arg)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead->pnext;int ret=0;while(pTmpnode!=NULL){ret=pFun(&pTmpnode->data,arg);if(ret!=0){break;}pTmpnode=pTmpnode->pnext;}return 0;
}

更新链表指定节点

int UpdateLinkList(LinkNode *pHead, DataType OldData, DataType NewData)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead->pnext;while(pTmpnode!=NULL){   if(pTmpnode->data==OldData){pTmpnode->data=NewData;}pTmpnode=pTmpnode->pnext;}return 0;
}

查找链表指定节点

LinkNode *FindLinkList(LinkNode *pHead, DataType TmpData)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead;while(pTmpnode->data!=TmpData){pTmpnode=pTmpnode->pnext;}return pTmpnode;
}

删除链表指定节点

int DeleteLinklist(LinkNode *pHead,DataType data)
{LinkNode *pTmpnode=NULL;LinkNode *pPreNode=NULL;pTmpnode=pHead;pPreNode=pHead;while(pTmpnode!=NULL){if((pTmpnode->data!=data)) //如果不是要被删除的节点{pPreNode=pTmpnode;//保存此节点pTmpnode=pTmpnode->pnext;//指向下一个节点}else{   //前一个节点的pnext指向要被删除节点的后一个节点pPreNode->pnext=pTmpnode->pnext;free(pTmpnode);//释放要被删除的节点pTmpnode=pPreNode->pnext;//循环遍历下一个节点}}return 0;}

销毁链表

int DestoryLinklist(LinkNode **pHead)
{LinkNode *pTmpnode=NULL;LinkNode *pTmpnext=NULL;pTmpnode=*pHead;while(pTmpnode!=NULL){  //保存下一个节点pTmpnext=pTmpnode->pnext;free(pTmpnode);//释放当前节点pTmpnode=pTmpnext; //指向下一个节点}*pHead=NULL;//头结点指向空return 0;
}

找到元素中间位置

算法：

       快指针pFast每次走2步
       慢指针pSlow每次走1步
       快指针到达末尾时，慢指针所在的位置即为中间位置

LinkNode *FindMidLinkNode(LinkNode *pHead)
{LinkNode *pFast=pHead->pnext;LinkNode *pSlow=pHead->pnext;while(pFast!=NULL){
//快节点先走两步，若是只有一个节点或两个节点，就跳出循环，此时慢节点指向第一个节点pFast=pFast->pnext;if(pFast==NULL){break;}pFast=pFast->pnext;if(pFast==NULL){break;}
//快节点走完两步，慢节点走一步pSlow=pSlow->pnext;}return pSlow;
}

 找到链表倒数第k个节点

算法：

         快指针先走k步
         慢指针和快指针每次走1步(快指针总是领先慢指针k步)
          当快指针走到末尾时,慢指针即指向链表倒数第k个节点

LinkNode *FindKthLinkNode(LinkNode *pHead,int k)
{int i=0;LinkNode *pFast=pHead->pnext;LinkNode *pSlow=pHead->pnext;
//快节点先走k步for(i=0;i<k;i++){pFast=pFast->pnext;if(pFast->pnext==NULL){return NULL;}}
//快慢节点每次都走1步，当快节点到达末尾时，慢节点的位置就是第k个节点while(pFast!=NULL){pFast=pFast->pnext;pSlow=pSlow->pnext;}return pSlow;
}

链表元素倒置

算法

        使用头插法将链表元素开始到结尾重新插入链表中，即第一个插入后第二个插入，第一个就在末尾，以此类推实现倒置

int ReverseLinkList(LinkNode *pHead)
{LinkNode *pInsertNode=pHead->pnext;LinkNode *pTmpNode=pHead->pnext;pHead->pnext=NULL;while(pTmpNode!=NULL){//保留革命火种pTmpNode=pTmpNode->pnext;//将剩余链表的第一个插入头结点pnextpInsertNode->pnext=pHead->pnext;pHead->pnext=pInsertNode;//插入节点向后移动pInsertNode=pTmpNode;}return 0;
}

链表元素排序

冒泡排序

int BubbleLinkList(LinkNode *pHead)
{LinkNode *ptmpNode1=NULL;LinkNode *ptmpNode2=NULL;LinkNode *pEnd=NULL;DataType pTmpData;
//没有元素或只有一个元素直接返回if(pHead->pnext==NULL ||pHead->pnext->pnext==NULL){return -1;}while(1){ptmpNode1=pHead->pnext;ptmpNode2=pHead->pnext->pnext;
//最后一次只有两个元素，此时链表已经排好序，pEnd和pTmpNode
相等，直接结束外层循环        if(ptmpNode2==pEnd){break;}//第一次排序结束时标志为pTmpNode=NULL,但是pEnd此时还是NULL,所以这里直接写成pEndwhile(ptmpNode2!=pEnd){
//相邻节点作比较，将大数往后挪if(ptmpNode1->data > ptmpNode2->data){pTmpData=ptmpNode1->data;ptmpNode1->data=ptmpNode2->data;ptmpNode2->data=pTmpData;}
//一直向后遍历ptmpNode1=ptmpNode1->pnext;ptmpNode2=ptmpNode2->pnext;}   
//当ptmpNode2走到NULL或者end时，ptmpNode1就是此时保存的数据最大节点，下一次就不用遍历此节点 pEnd=ptmpNode1;}return 0;
}

选择排序

pTmpNode负责遍历后面的节点，当找到比pMinNode节点更小的值时，更新pMinNode,然后比较pSwapNode与pMinNode值的大小，将小的值存放在pSwapNode节点的数据中，pSwap再指向像一个节点，进行下一轮比较

//选择排序
int SelectSortLinkList(LinkNode *pHead)
{LinkNode *pSwapNode=pHead->pnext;LinkNode *pMinNode=pHead->pnext;LinkNode *pTmpNode=NULL;DataType TmpData;if(pHead->pnext==NULL){return 0;}while(pSwapNode->pnext!=NULL){
//每次先将pMinNode保存为待交换的节点pMinNode=pSwapNode;
//从待交换节点的下一个节点开始遍历pTmpNode=pSwapNode->pnext;
//找到后面最小的数据的节点，将每一个遍历的节点都与最小节点比较，让pMinNode总是指向更小的节点while(pTmpNode!=NULL){if(pMinNode->data >pTmpNode->data ){pMinNode=pTmpNode;}pTmpNode=pTmpNode->pnext;}
//如果最小的数据比带交换数据还小，就交换两个节点的数据，保证此轮最小的数据在最前面if(pMinNode->data < pSwapNode->data){TmpData=pMinNode->data;pMinNode->data=pSwapNode->data;pSwapNode->data=TmpData;}
//待交换数据向后依次遍历pSwapNode=pSwapNode->pnext;}return 0;
}

如何判断一个链表是否有环？环长？环的入口位置？

是否有环：

        快指针每次走2步,慢指针每次走1步,快慢指针相遇则说明有环
如何计算环长：

        标记相遇的位置，让指针继续向后走，没走一步计算器自加,走回到标记位置，则计算器值即为环长
如何计算环入口位置：

        将一个指针从第一个节点向后走，将一个指针从相遇点向后走，两个指针相遇的位置即为环入口的位置

LinkNode *IsHasCircle(LinkNode *pHead,int *len)
{int ret=0;*len=1;LinkNode *pFast=NULL;LinkNode *pSlow=NULL;LinkNode *pTmpNode=NULL;LinkNode *pNode1=NULL;LinkNode *pNode2=NULL;pFast=pSlow=pHead->pnext;
//判断是否有环while(1){pFast=pFast->pnext;if(pFast==NULL){ret=0;break;}pFast=pFast->pnext;if(pFast==NULL){ret=0;break;}pSlow=pSlow->pnext;if(pFast==pSlow){ret=1;break;}}if(ret==1){//获得环长
//从相遇节点的下一个节点触发，再次走到相遇节点刚好走路一圈pTmpNode=pSlow->pnext;while(pTmpNode!=pSlow){(*len)++;pTmpNode=pTmpNode->pnext;}获得环入口节点
//pNode1从第一个节点开始向后走pNode1=pHead->pnext;
//pNode2从快慢相遇位置开始走（在环内走）pNode2=pSlow;
//pNode1和pNode2节点相遇的位置即为环入口节点while(pNode1!=pNode2){pNode1=pNode1->pnext;pNode2=pNode2->pnext;}return pNode1;}return NULL;
}