单链表 （面试题）

时间：2022-11-03 09:41:00

关于单链表的基本操作，之前已经总结过了，那些掌握之后算是了解了单链表是什么？不过现在面试的题中，肯定不会只让你回答单链表的基础操作，总是会改变一些东西，或是扩展一下。

下面就是一些关于单链表的扩展内容：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#pragma warning (disable:4996)
#define DataType int
typedef struct PNode{
 DataType data;
 struct PNode* next;
}Node,*PNode;
//创建新的节点
PNode BuyNode(DataType data);
//初始化单链表
void InitList(PNode* pHead);
//尾插
void PushList(PNode* pHead, DataType data);
//打印单链表
void PrintList(PNode pHead);
// 从尾到头打印单链表
void PrintListFromTail2Head(PNode pHead);
// 删除无头单链表的非尾结点
void DeleteNotTailNode(PNode pos);
// 在无头单链表非头结点前插入置为data的结点
void InsertNotHeadNode(PNode pos, DataType data);
// 用单链表实现约瑟夫环
PNode JosephCircle(PNode pHead, size_t M);
// 逆置单链表--三个指针
PNode ReverseList(PNode pHead);
// 逆置单链表--头插法
PNode ReverseList_P(PNode pHead);
// 对单链表进行冒泡排序--升序
void BubbleSort(PNode pHead);
// 查找单链表的中间结点，要求只能够遍历一次链表
PNode FindMidNode(PNode pHead);
// 查找单链表的倒数第K个结点，只能够遍历一次链表
PNode FindLastKNode(PNode pHead, size_t K);
//// 删除单链表的倒数第K个结点
//PNode DeleteLastKNode(PNode pHead, size_t K);
//
//// 合并两个已序单链表，合并之后依然有序
//PNode MergeList(PNode pHead1, PNode pHead2);

有些内容就不能按照常规的思路来看，我记得第一次上课的时候，老师出了一道智力题，

说是有两只分布不均匀的香，但是它们都能燃烧一个小时，如果我们想要测量一刻钟的时间，该如何做？

当时很多人都说将香掐成两段，然而，香并不是均匀的，所以不行。

最后给出了答案：将两只香同时点燃，不过，要一只点燃一头，另一只点燃两头，这样，等其中一只燃烧完了之后，时间刚好过了半个小时，再将另一头也点上，这样，剩余的香就能燃烧一刻钟的时间了。

同样的道理，这里的一些问题也是这样的想法，比如求中点的问题，只要给出两个指针，慢的一次走一步，快的一次走两步，等快的走到最后，那么慢的刚好走到中间。

下面就是这些函数的实现了：



#include"LinkList.h" //创建新的节点 PNode BuyNode(DataType data) { PNode Node = (PNode)malloc(sizeof(Node)); if (Node) { Node->data = data; Node->next = NULL; } return Node; } //初始化单链表 void InitList(PNode * pHead) { assert(pHead); (*pHead) = NULL; } //尾插 void PushList(PNode* pHead, DataType data) { assert(pHead); PNode NewNode = BuyNode(data); if (NULL==(*pHead)) { (*pHead) = NewNode; } else { PNode pCur = (*pHead); while (pCur->next) { pCur = pCur->next; } pCur->next = NewNode; } } void PrintList(PNode pHead) { PNode pCur = pHead; while (pCur) { printf("%d ", pCur->data); pCur = pCur->next; } printf("\n"); } // 从尾到头打印单链表 void PrintListFromTail2Head(PNode pHead) { if (pHead) { PrintListFromTail2Head(pHead->next);//运用递归的思想，找出最后一个节点，打印 printf("%d ", pHead->data); } printf("\n"); } // 删除无头单链表的非尾结点，不能遍历单链表 void DeleteNotTailNode(PNode pos) { if (NULL == pos)//如果pos的位置为空，直接返回 { return; } PNode pDel = pos->next;//将pos后面的节点保存 pos->data = pDel->data;//将pos后面的值，赋给pos中的data pos->next = pDel->next;//将pos的下一个位置指向待删除的下一个位置 free(pDel);//释放空间 } // 在无头单链表非头结点前插入置为data的结点 void InsertNotHeadNode(PNode pos, DataType data) { if (NULL == pos) { return; } PNode NewNode = BuyNode(pos->data); if (NewNode) { NewNode->next = pos->next; pos->next = NewNode; pos->data = data; } } // 用单链表实现约瑟夫环 PNode JosephCircle(PNode pHead, size_t M) { if (NULL == pHead) { return; } PNode pCur = pHead; while (pCur != pCur->next) { size_t k = M; while (--k) { pCur = pCur->next; } PNode pDel = pCur->next; pCur->data = pDel->data; pCur->next = pDel->next; free(pDel); } return pCur; } // 逆置单链表--三个指针 PNode ReverseList(PNode pHead)//不太理解 { if (NULL == pHead || NULL == pHead->next) { return pHead; } PNode prev = pHead; PNode pCur = prev->next; PNode pnext = pCur->next; while (pnext) { pCur->next = prev; prev = pCur; pCur = pnext; pnext = pnext->next; } pCur->next = prev; pHead->next = NULL; return pCur; } // 逆置单链表--头插法 PNode ReverseList_P(PNode pHead) { if (NULL == pHead || NULL == pHead->next) { return NULL; } PNode pCur = pHead->next; PNode NewNode = NULL; while (pCur) { pHead->next = NewNode; NewNode = pHead; pHead = pCur; pCur = pCur->next; } pHead->next = NewNode; NewNode = pHead; return NewNode; } // 对单链表进行冒泡排序--升序 void BubbleSort(PNode pHead) { if (NULL == pHead || NULL == pHead->next) { return; } PNode pCur = pHead; PNode pTail = NULL; DataType flag = 0; while (pTail != pHead) { pCur = pHead; while (pCur->next != pTail) { //结构体中的next定义成PNode*的形式，才能使next继续间接访问， if ((pCur->data) > (pCur->next->data)) { DataType temp = pCur->data; //交换 pCur->data = pCur->next->data; pCur->next->data = temp; flag = 1; } pCur = pCur->next; } if (!flag) { return; } pTail = pCur; } } // 查找单链表的中间结点，要求只能够遍历一次链表 PNode FindMidNode(PNode pHead) { if (NULL == pHead || NULL == pHead->next) { return; } //使用一快一慢两个指针，快的是慢的的二倍 PNode pslow = pHead; PNode pfast = pHead; while (pfast&&pfast->next)//分两种情况考虑 { pslow = pslow->next; pfast = pfast->next->next; } return pslow;//快的指针到尾部，慢的指针就在中间，所以返回慢的指针即可 } // 查找单链表的倒数第K个结点，只能够遍历一次链表 PNode FindLastKNode(PNode pHead, size_t K) { if (NULL == pHead || K == 0) { return NULL; } PNode pslow = pHead; PNode pfast = pHead; while (--K)//先让快的指针走K步 { if (NULL == pfast)//如果K的值大于节点数，返回空 { return NULL; } pfast = pfast->next; } while (pfast->next)//再一起走，等到快的走到尾部，慢的刚好到倒数第K个节点 { pfast = pfast->next; pslow = pslow->next; } return pslow;//返回慢的指针即可 } //删除单链表的倒数第K个结点 PNode DeleteLastKNode(PNode pHead, size_t K) { if (NULL == pHead || NULL == pHead->next) { return NULL; } PNode pos = FindLastKNode(pHead, K); Earse(pHead, pos); } //合并两个已序单链表，合并之后依然有序 PNode MergeList(PNode pHead1, PNode pHead2) { if (NULL == pHead1) { return pHead2; } if (NULL == pHead2) { return pHead1; } PNode pTail= NULL; PNode NewNode = NULL; if (pHead1->data < pHead2->data) { pTail = pHead1; pHead1 = pHead1->next; } else { pTail = pHead2; pHead2 = pHead2->next; } NewNode = pTail; while (pHead1&&pHead2) { if (pHead1->data < pHead2->data) { pTail->next = pHead1; pTail = pHead1; pHead1 = pHead1->next; } else { pTail->next = pHead2; pTail = pHead2; pHead2 = pHead2->next; } } if (pHead1) { pTail->next = pHead1; } else { pTail->next = pHead2; } return NewNode; }

#include"LinkList.h"
void FunTest()
{
 PNode pHead;
 InitList(&pHead);
 PushList(&pHead,5);
 PushList(&pHead, 8);
 PushList(&pHead, 2);
 PushList(&pHead, 7);
 PushList(&pHead, 9);
 PrintList(pHead);
 PrintListFromTail2Head(pHead);
 //
 //JosephCircle(pHead, 3);
 //PrintListFromTail2Head(pHead);
 PNode p=FindMidNode(pHead);
 printf("%d\n", p->data);
 PNode p1 = FindLastKNode(pHead, 1);
 printf("%d\n", p1->data);
 BubbleSort(pHead);
 PrintList(pHead);
}
int main()
{
 FunTest();
 system("pause");
 return 0;
}

程序写的很欠缺，有的地方还需再进行，如果，你们有什么意见或建议，请评论……

标签：

相关文章