链表的基本操作——以及链表面试题

#define _CRT_SECURE_NO_WARNINGS#include"list.h"
#include<assert.h>void SListInit(PNode* pHead) //链表初始化
{assert(pHead);*pHead &＃61; NULL;
}PNode BuySListNode(DataType data)//申请一个结点
{PNode PNewNode &＃61; (PNode )malloc(sizeof(Node));if (PNewNode &＃61;&＃61; NULL){return NULL;}PNewNode->_pNext &＃61; NULL;PNewNode->_data &＃61; data;return PNewNode;
}void SListPushBack(PNode* pHead, DataType data)// 尾插
{assert(pHead);if (NULL &＃61;&＃61; pHead){/*pHead &＃61; BuySListNode(data);*/return;}else{PNode pCur &＃61; NULL;pCur &＃61; *pHead;while (pCur->_pNext){pCur &＃61; pCur->_pNext;}pCur->_pNext &＃61; BuySListNode(data);}
}void SListPopBack(PNode* pHead) // 尾删
{assert(pHead);if (NULL &＃61;&＃61; *pHead) //空链表return ;else if (NULL &＃61;&＃61; (*pHead)->_pNext) //只有一个节点{PNode TmpNode &＃61; *pHead;free(TmpNode);TmpNode &＃61; NULL;*pHead &＃61; NULL;}else{PNode pCur &＃61; *pHead;while (pCur->_pNext->_pNext){pCur &＃61; pCur->_pNext;}pCur->_pNext &＃61; NULL;}
}void SListPushFront(PNode* pHead, DataType data)// 头插
{PNode PNewNode &＃61; NULL;assert(pHead);PNewNode &＃61; BuySListNode(data);if (NULL &＃61;&＃61; PNewNode)return;PNewNode->_pNext &＃61; *pHead;*pHead &＃61; PNewNode;}void SListPopFront(PNode* pHead)// 头删
{PNode pDelNode &＃61; NULL;assert(pHead);if (NULL &＃61;&＃61; pHead) //空链表return ;pDelNode &＃61; *pHead;*pHead &＃61; pDelNode->_pNext;free(pDelNode);
}// 查找值为data的结点&＃xff0c;返回该结点在链表中的位置
PNode SListFind(PNode pHead, DataType data)
{PNode pCur &＃61; pHead;while (pCur){if (pCur->_data &＃61;&＃61; data){return pCur;}pCur &＃61; pCur->_pNext;}return NULL;
}// 在链表pos位置后插入结点data
void SListInsert(PNode* pHead, PNode pos, DataType data)
{PNode PNewNode &＃61; NULL;assert(pHead);if (NULL &＃61;&＃61; *pHead || NULL &＃61;&＃61; pos)return;PNewNode &＃61; BuySListNode(data);PNewNode->_pNext &＃61; pos->_pNext;pos->_pNext &＃61; PNewNode;}// 删除链表pos位置上的结点
void SListErase(PNode* pHead, PNode pos)
{assert(pHead);if (NULL &＃61;&＃61; *pHead || NULL &＃61;&＃61; pos)return;if (pos &＃61;&＃61; *pHead){SListPopFront(pHead);}else{PNode pCur &＃61; *pHead;while (pCur && pCur->_pNext !&＃61; pos){pCur &＃61; pCur->_pNext;}if (pCur){pCur->_pNext &＃61; pos->_pNext;free(pos);}}
}void SListClear(PNode* pHead)// 将链表中的结点清空
{PNode pDelNode &＃61; NULL;assert(pHead);while (*pHead){pDelNode &＃61; *pHead;*pHead &＃61; pDelNode->_pNext;free(pDelNode);}
}void SListDestroy(PNode* pHead)// 销毁单链表
{SListClear(pHead);
}int SListSize(PNode pHead) // 求链表中结点的个数
{int count &＃61; 0;PNode pCur &＃61; pHead;assert(pHead);if (NULL &＃61;&＃61; pHead)return 0;pCur &＃61; pHead;while (pCur){count&＃43;&＃43;;pCur &＃61; pCur->_pNext;}return count;
}// 获取链表中的最后一个结点&＃xff0c;返回该结点的地址
PNode SListBack(PNode pHead)
{PNode pCur &＃61; pHead;assert(pHead);while (pCur->_pNext){pCur &＃61; pCur->_pNext;}return pCur;
}void PrintList(PNode* pHead)//打印单链表
{PNode pCur &＃61; *pHead;while (pCur){printf("%d->", pCur->_data);pCur &＃61; pCur->_pNext;}printf("NULL\n");
}

以下为链表面试题

// 从尾到头打印单链表
void PrintListFromTail2Head(PNode pHead)
{if (pHead){PrintListFromTail2Head(pHead->_pNext);printf("%d--", pHead->_data);}
}// 删除无头单链表的非尾结点&＃xff0c;要求&＃xff1a;不能遍历链表
void DeleteNotTailNode(PNode pos)
{PNode pDelNode &＃61; NULL;if (NULL &＃61;&＃61; pos&&NULL &＃61;&＃61; pos->_pNext)return;pDelNode &＃61; pos->_pNext;pos->_data &＃61; pDelNode->_data;pos->_pNext &＃61; pDelNode->_pNext;free(pDelNode);
}// 在无头单链表pos位置前插入值为结点data的结点 (不能遍历链表)
void InsertPosFront(PNode pos, DataType data)
{PNode pNewNode &＃61; NULL;if (NULL &＃61;&＃61; pos)return;pNewNode &＃61; BuySListNode(pos->_data);pNewNode->_pNext &＃61; pos->_pNext;pos->_pNext &＃61; pNewNode;pos->_data &＃61; data;
}// 用单链表模拟实现约瑟夫环
void JosephCircle(PNode* pHead, const int M)
{assert(pHead);PNode pCur &＃61; *pHead;if (NULL &＃61;&＃61; pHead)return;while (pCur->_pNext !&＃61; pCur){///报数int count &＃61; M;while (--count){pCur &＃61; pCur->_pNext;}//删除--替换法删除PNode pDelNode &＃61; pCur->_pNext;pCur->_data &＃61; pDelNode->_data;pCur->_pNext &＃61; pDelNode->_pNext;free(pDelNode);}*pHead &＃61; pCur;
}// 使用冒泡排序方法对单链表进行排序
void BubbleSort(PNode pHead)
{PNode pPreCur &＃61; NULL;PNode pCur &＃61; NULL;PNode pTail &＃61; NULL;if (NULL &＃61;&＃61; pHead || NULL &＃61;&＃61; pHead->_pNext)return;while (pHead !&＃61; pTail){int IsChange &＃61; 0;pPreCur &＃61; pHead;pCur &＃61; pPreCur->_pNext;while (pCur !&＃61; pTail){if (pPreCur->_data > pCur->_data){int tmp &＃61; pPreCur->_data;pPreCur->_data &＃61; pCur->_data;pCur->_data &＃61; tmp;IsChange &＃61; 1;}pPreCur &＃61; pCur;pCur &＃61; pPreCur->_pNext;}if (!IsChange)return;pTail &＃61; pPreCur;}
}// 单链表的逆置--三个指针
void ReverseSList(PNode* pHead)
{PNode pPre &＃61; NULL;PNode pCur &＃61; NULL;PNode pNext &＃61; NULL;assert(pHead);if (NULL &＃61;&＃61; *pHead || NULL &＃61;&＃61; (*pHead)->_pNext)return;pCur &＃61; *pHead;while (pCur){pNext &＃61; pCur->_pNext;pCur->_pNext &＃61; pPre;pPre &＃61; pCur;pCur &＃61; pNext;}*pHead &＃61; pPre;
}// 单链表的逆置--头插法
PNode ReverseSListOP(PNode pHead)
{PNode pNewHead &＃61; NULL;PNode pCur &＃61; pHead;PNode pNext &＃61; NULL;if (NULL &＃61;&＃61; pHead || NULL &＃61;&＃61; pHead->_pNext)return pHead;while (pCur){pNext &＃61; pCur->_pNext;pCur->_pNext &＃61; pNewHead;pNewHead &＃61; pCur;pCur &＃61; pNext;}return pNewHead;
}// 合并两个有序链表&＃xff0c;合并之后依然有序
PNode MergeSList(PNode pHead1, PNode pHead2)
{PNode pNewHead &＃61; NULL;PNode pTailNode &＃61; NULL;PNode pL1 &＃61; pHead1;PNode pL2 &＃61; pHead2;if (NULL &＃61;&＃61; pHead1)return pHead2;if (NULL &＃61;&＃61; pHead2)return pHead1;//两个链表都不为空&＃xff0c;确定第一个节点if (pL1->_data < pL2->_data){pNewHead &＃61; pL1;pL1 &＃61; pL1->_pNext;}else{pNewHead &＃61; pL2;pL2 &＃61; pL2->_pNext;}//向新链表中插入值pTailNode &＃61; pNewHead;while (pL1 && pL2){if (pL1->_data < pL2->_data){pTailNode->_pNext &＃61; pL1;pL1 &＃61; pL1->_pNext;}else{pTailNode->_pNext &＃61; pL2;pL2 &＃61; pL2->_pNext;}pTailNode &＃61; pTailNode->_pNext;}//若一个链表有剩余&＃xff0c;放在新链表后面if (pL1)pTailNode->_pNext &＃61; pL1;elsepTailNode->_pNext &＃61; pL2;return pNewHead;
}// 查找链表的中间结点&＃xff0c;要求只能遍历一次链表
PNode FindMiddleNode(PNode pHead)
{PNode pFast &＃61; pHead;PNode pSlow &＃61; pHead;/*PNode pPre &＃61; pHead;*/while (pFast && pFast->_pNext){/*pPre &＃61; pSlow;*/pFast &＃61; pFast->_pNext->_pNext;pSlow &＃61; pSlow->_pNext;}//求奇数个节点的中间节点前一个节点/*if (NULL &＃61;&＃61; pFast)return pPre;*/return pSlow;
}// 查找链表的倒数第K个结点&＃xff0c;要求只能遍历链表一次
PNode FindLastKNode(PNode pHead, int K)
{PNode pFast &＃61; pHead;PNode pSlow &＃61; pHead; if (NULL &＃61;&＃61; pHead || K < 0)return NULL;//让pFast先走K步while (K--){if (NULL &＃61;&＃61; pFast)//K大于节点个数return NULL;pFast &＃61; pFast->_pNext;}//两指针同时往后走while (pFast){pFast &＃61; pFast->_pNext;pSlow &＃61; pSlow->_pNext;}return pSlow;
}// 删除链表的倒数第K个结点&＃xff0c;要求只能遍历链表一次
PNode DeleteLastKNode(PNode pHead, int K)
{PNode pFast &＃61; pHead;PNode pSlow &＃61; pHead;PNode pPre &＃61; NULL;if (NULL &＃61;&＃61; pHead || K <&＃61; 0)return NULL;int count &＃61; K;//快的指针先走K步while (count--){if (NULL &＃61;&＃61; pFast)return NULL;pFast &＃61; pFast->_pNext;}//然后快慢指针一起走&＃xff0c;慢指针指向的就是倒数第K个节点while (pFast){pPre &＃61; pSlow;pFast &＃61; pFast->_pNext;pSlow &＃61; pSlow->_pNext;}//删除pPre->_pNext &＃61; pSlow->_pNext;free(pSlow);return pHead;
}// 判断单链表是否相交&＃xff1f;链表不带环
int IsCrossWithoutCircle(PNode pHead1, PNode pHead2)
{PNode pTail1 &＃61; pHead1;PNode pTail2 &＃61; pHead2;if (NULL &＃61;&＃61; pHead1 || NULL &＃61;&＃61; pHead2)return 0;//找第一个链表的最后一个节点while (pTail1)pTail1 &＃61; pTail1->_pNext;//找第二个链表的最后一个节点while (pTail2)pTail2 &＃61; pTail2->_pNext;return pTail1 &＃61;&＃61; pTail2;
}// 求不带环单链表相交交点
PNode GetCrossNode(PNode pHead1, PNode pHead2)
{int size1 &＃61; 0, size2 &＃61; 0, gap;PNode pCur1 &＃61; pHead1, pCur2 &＃61; pHead2;if (!(IsCrossWithoutCircle(pHead1, pHead2)))return NULL;//求交点while (pCur1){size1&＃43;&＃43;;pCur1 &＃61; pCur1->_pNext;}while (pCur2){size2&＃43;&＃43;;pCur2 &＃61; pCur2->_pNext;}//让长的链表先走差值这么多gap &＃61; size1 - size2;pCur1 &＃61; pHead1; pCur2 &＃61; pHead2;if (gap > 0){while (gap--)pCur1 &＃61; pCur1->_pNext;}else{while (gap&＃43;&＃43;)pCur2 &＃61; pCur2->_pNext;}while (pCur1 !&＃61; pCur2){pCur1 &＃61; pCur1->_pNext;pCur2 &＃61; pCur2->_pNext;}return pCur1;
}// 判断链表是否带环
PNode IsCircle(PNode pHead)
{PNode pFast &＃61; pHead;PNode pSlow &＃61; pHead;while (pFast&&pFast->_pNext){pFast &＃61; pFast->_pNext->_pNext;pSlow &＃61; pSlow->_pNext;if (pFast &＃61;&＃61; pSlow) //带环return pFast;}return 0;
}// 求环的长度
int GetCircleLen(PNode pHead)
{PNode pMeetNode &＃61; IsCircle(pHead);PNode pCur &＃61; pMeetNode;int count &＃61; 1;if (NULL &＃61;&＃61; pMeetNode)return 0;while (pCur->_pNext !&＃61; pMeetNode){count&＃43;&＃43;;pCur &＃61; pCur->_pNext;}return count;
}// 求环的入口点--注意推断过程
PNode GetEnterNode(PNode pHead, PNode pMeetNode)
{PNode PH &＃61; pHead;PNode PM &＃61; pMeetNode;if (NULL &＃61;&＃61; pHead || NULL &＃61;&＃61; pMeetNode)return NULL;while (PH !&＃61; PM){PH &＃61; PH->_pNext;PM &＃61; PM->_pNext;}return PM;
}// 判断链表是否带环&＃xff0c;链表可能带环
int IsListCrossWithCircle(PNode pHead1, PNode pHead2)
{PNode pMeetNode1 &＃61; NULL;PNode pMeetNode2 &＃61; NULL;if (NULL &＃61;&＃61; pHead1 || NULL &＃61;&＃61; pHead2)return 0;//判断两个链表是否带环pMeetNode1 &＃61; IsCircle(pHead1);pMeetNode2 &＃61; IsCircle(pHead2);//两个链表都不带环if (NULL &＃61;&＃61; pMeetNode1&&NULL &＃61;&＃61; pMeetNode2){//求两个链表的最后一个元素&＃xff0c;若最后一个元素相等则相交PNode pTail1 &＃61; pHead1;PNode pTail2 &＃61; pHead2;while (pTail1->_pNext)pTail1 &＃61; pTail1->_pNext;while (pTail2->_pNext)pTail2 &＃61; pTail2->_pNext;if (pTail1 &＃61;&＃61; pTail2)return 1;}//两个链表都带环else if (pMeetNode1 && pMeetNode2){PNode pCur &＃61; pMeetNode1;/* do{if (pCur &＃61;&＃61; pMeetNode2)return 2;pCur &＃61; pCur->_pNext;} while (pCur !&＃61; pMeetNode1);*/while (pCur->_pNext !&＃61; pMeetNode1){if (pCur &＃61;&＃61; pMeetNode2)return 2;pCur &＃61; pCur->_pNext;}if (pCur &＃61;&＃61; pMeetNode2)return 2;}return 0;
}// 复杂链表的复制
PCListNode CopyComplexList(PCListNode pHead)
{PCListNode pOldNode &＃61; pHead;PCListNode pNewNode &＃61; NULL;PCListNode pNewHead &＃61; NULL;if (NULL &＃61;&＃61; pHead)return NULL;//在原链表的每个节点后插入值相同的新节点while (pOldNode){pNewHead &＃61; (PCListNode)malloc(sizeof(CListNode));pNewHead->_data &＃61; pOldNode->_data;pNewNode->_pNext &＃61; NULL;pNewNode->_pRandom &＃61; NULL;if (NULL &＃61;&＃61; pNewNode)return NULL;pNewNode->_pNext &＃61; pOldNode->_pNext;pOldNode->_pNext &＃61; pNewNode;pOldNode &＃61; pNewNode->_pNext;}//给新插入的节点的随机指针域赋值pOldNode &＃61; pHead;while (pOldNode){pNewNode &＃61; pOldNode->_pNext;if (NULL &＃61;&＃61; pOldNode->_pRandom)pNewNode->_pRandom &＃61; NULL;elsepNewNode->_pRandom &＃61; pOldNode->_pRandom->_pNext;pOldNode &＃61; pNewNode->_pNext;}//将插入的新节点从链表中拆下来pOldNode &＃61; pHead;pNewHead &＃61; pOldNode->_pNext;while (pOldNode->_pNext){pNewNode &＃61; pOldNode->_pNext;pOldNode->_pNext &＃61; pNewNode->_pNext;pOldNode &＃61; pNewNode;}return pNewHead;
}