# 常见链表面试题

``````typedef int DataType;

typedef struct SlistNode{
DataType data;
struct SlistNode *pNext;
}Slist, *PNode;``````

1. 逆序打印带头结点的单链表

``````void PrintListFromTail2Head(PNode pHead)//逆序打印链表
{
//递归
}

//非递归  用栈先进后出的特性
}``````

2.头插（不带头结点）

``````void InsertFront(PNode pos, DataType data)
{
PNode pNewNode = NULL;
if(NULL == pos)
return;

pNewNode->_pNext = pos->_pNext;
pos->_pNext = pNewNode;
pos->_data = data;
}``````

3.单链表模拟实现约瑟夫环

1、构建环，头尾节点相连
2、报数，找到要删除的节点
3、删除节点——找到要删除节点的下一节点

pCur指向pDel下一节点，删除pDel

``````void JosephCircle(PNode* pHead, size_t M)//用单链表模拟实现约瑟夫环
{
PNode pCur = NULL;
PNode pTailNode = NULL;
return;

//构建环，尾结点和头结点相连
while (pTailNode->pNext){//找到尾结点
pTailNode = pTailNode->pNext;
}

while (pCur != pCur->pNext){
size_t count = M;
PNode pDel = NULL;
while (--count){
pCur = pCur->pNext;
}
//删除pCur节点，此处将pCur改成其下一节点，删除它的下一节点
pDel = pCur->pNext;
pCur->data = pDel->data;
pCur->pNext = pDel->pNext;
free(pDel);
}
}
``````

4、单链表的逆置——就地逆置

``````void ReverseList(PNode* pHead)//逆置单链表   三个指针
{
PNode pPre = NULL;
PNode pCur = NULL;
PNode pNextNode = NULL;
return;

while (pCur){
pNextNode = pCur->pNext;//标记下一个节点
pCur->pNext = pPre;//将当前节点指向下一节点的指针 指向前一个节点
pPre = pCur;//Pre节点往前移
pCur = pNextNode;//当前节点往前移
}
}
``````

5.头插法逆置

``````
{
PNode pNextNode = NULL;

while (pCur)
{
pNextNode = pCur->pNext;//标记下一节点
pCur = pNextNode;
}

}``````

6.冒泡排序

``````void BubbleSort(PNode pHead)//冒泡排序
{
PNode pCur = NULL;
PNode pNextNode = NULL;
PNode pTail = NULL;//用pTail来标记还没排好序的链表的尾结点
int flag = 0;//设标签优化

pNextNode = pCur->pNext;
while (pNextNode != pTail){
if (pCur->data > pNextNode->data){
pCur->data = (pCur->data) ^ (pNextNode->data);
pNextNode->data = (pCur->data) ^ (pNextNode->data);
pCur->data = (pCur->data) ^ (pNextNode->data);
flag = 1;
}
pCur = pNextNode;
pNextNode = pCur->pNext;
}
if (!flag)//如果标签为0则表示链表已是有序的，直接返回
return;

pTail = pCur;//标记还没排好序的链表的尾结点
}
}
``````

7.只遍历一次链表查找单链表的中间结点

``````
{
//快慢指针，快指针一次走两步
while (pFast->pNext){
pSlow = pSlow->pNext;
pFast = pFast->pNext->pNext;
}
return pSlow;
}``````

8.查找倒数第K个节点

``````
PNode FindLastKNode(PNode pHead, size_t K)// 查找链表的倒数第K个结点
{
//快慢指针，快指针先走K节点
while (K--)
{
pFast = pFast->pNext;
}
while (pFast)
{
pSlow = pSlow->pNext;
pFast = pFast->pNext;
}
return pSlow;
}
``````

9.删除倒数第K个节点

``````先找到倒数第K个节点，再删除
int DeleteLastKNode(PNode* ppHead, size_t K)// 删除单链表的倒数第K个结点
{
PNode pPreSlow = NULL;
while (K--)
{
if (pFast == NULL)
return;
pFast = pFast->pNext;
}
while (pFast)
{
pPreSlow = pSlow;//标记下pSlow的前一个节点
pSlow = pSlow->pNext;
pFast = pFast->pNext;
}
pPreSlow->pNext = pSlow->pNext;
free(pSlow);
return 1;
}
``````

10.合并两个有序链表

``````PNode MergeList(PNode pHead1, PNode pHead2)// 合并两个已序链表
{
PNode pTail = NULL;

//若两链表不为空，先定义新的头结点
if (pCur1->data < pCur2->data){
pCur1 = pCur1->pNext;
}
else{
pCur2 = pCur2->pNext;
}
while (pCur1 && pCur2){
if (pCur1->data < pCur2->data){
pTail->pNext = pCur1;
pCur1 = pCur1->pNext;
}
else{
pTail->pNext = pCur2;
pCur2 = pCur2->pNext;
}
pTail = pTail->pNext;
}//end while()
//循环结束，若还有链表没有走完，则接上
if (pCur1)
pTail->pNext = pCur1;
if (pCur2)
pTail->pNext = pCur2;