数据结构学习（C++）――如何在一个链表中链入不同类型的对象数据结构学习（C++）――如何在一个链表中链入不同类型的对象
似乎你也注意到了，不管怎么定义，好像一个链表中的对象都是同一类型的。而实际上，这也是必须的，否则，返回节点中的数据这样的函数的返回值的类型是什么呢？但是，人的要求是无止境的……（省略本人感慨若干百字）。把不同的对象链在一个链表中的目的是为了方便使用，现在一定记住这个原则，后面的讨论都是基于这个原则的，否则，我们就是技术狂人了――偏偏实现一些看起来不可能的事情。达到这个目标的原理其实很简单，只要把不同类型的对象变成同样的类型就可以了。看下面的结构定义：struct Mobject{&&&&&& void *p;&&&&&& int ObjectT};将一个对象链入链表时，将指向这个对象的指针赋给p，同时记录对象类型。当取得这个节点的时候，根据ObjectType的值来确定p指的对象类型，从而还原指针类型，也就得到了原来的对象。后面讲到的广义表实际上采用的就是这种方法。显而易见的，这样的Mobject支持的对象是预先确定的，你将自己维护ObjectType列表，每添加一种类型的支持，你需要在ObjectType列表中给出它的替代值，然后在相应的switch(ObjectType)给出这种类型的case语句。很烦人是吧，下面给出另一种方法，其实还是这个原理，不同的是，把这个烦人的工作交给编译器了。还记得前边强调的原则吗，为什么我们将不同类型的对象放在一个链表中呢？很显然，我们想达到这样的一个效果：比如说，我们在一个链表中储存了三角形，直线，圆等图形的参数，我们希望对某个节点使用Draw()方法，就重绘这个图形；使用Get()则得到这个图形的各个参数；使用Put()则修改图形的参数。可以看出，这些不同的对象实际上有同样的行为，只是实现的方法不同。C++的多态性正好可以实现我们的构想。关于这方面，请参阅相关的C++书籍（我看的是《C++编程思想》）。请看如下的例子：#ifndef Shape_H#define Shape_H&class Shape& {public:&&&&&& virtual void Input() = 0;&&&&&& virtual void Print() = 0;&&&&&& Shape(){};&&&&&& virtual ~Shape(){};&};&#endif【说明】定义一个抽象基类，有两个行为，Input()为输入图形参数，Print()为打印图形参数。图省事，只是简单的说明问题而已。#ifndef Point_H#define Point_H&class Point& {public:&&&&&& void Put()&&&&&& {&&&&&&&&&&&&& cout && "x坐标为：";&&&&&& &&&&&& cin &&&&&&&&&&&&&&& cout && "y坐标为：";&&&&&&&&&&&&& cin &&&&&&&& }&&&&&& &&&&&& void Get()&&&&&& {&&&&&&&&&&&&& cout && endl && "x坐标为：" &&&&&&&&&&&&&&& cout && endl && "y坐标为：" &&&&&&&& }&&&&&& &&&&&& virtual ~Point(){};&private:&&&&&& &&&&&& };&#endif【说明】点的类定义与实现。#ifndef Circle_H#define Circle_H&#include "Shape.h"#include "Point.h" &class Circle : public Shape& {public:&&&&&& void Input()&&&&&& {&&&&&&&&&&&&& cout && endl && "输入圆的参数";&&&&&&&&&&&&& cout && endl && "输入圆心点的坐标：" &&&&&&&& &&&&&& center.Put();&&&&&&&&&&&&& cout && endl && "输入半径：";&&&&&&&&&&&&& cin &&&&&&&& }&&&&&&& void Print()&&&&&& {&&&&&&&&&&&&& cout && endl && "圆的参数为";&&&&&&&&&&&&& cout && endl && "圆心点的坐标：" &&&&&&&& &&&&&& center.Get();&&&&&&&&&&&&& cout && endl && "半径：" &&&&&&&& }&&&&& &&&&&& virtual ~Circle(){};&private:&&&&&& &&&&&& P};&#endif【说明】圆的类定义与实现。继承Shape类的行为。#ifndef Line_H#define Line_H&#include "Shape.h"#include "Point.h"&class Line : public Shape {public:&&&&&& void Input()&&&&&& {&&&&&&&&&&&&& cout && endl && "输入直线的参数";&&&&&&&&&&&&& cout && endl && "输入端点1的坐标：" &&&&&&&& &&&&&& point1.Put();&&&&&&&&&&&&& cout && endl && "输入端点2的坐标：" &&&&&&&& &&&&&& point2.Put();&&&&&& }&&&&&& &&&&&& void Print()&&&&&& {&&&&&&&&&&&&& cout && endl && "直线的参数为";&&&&&&&&&&&&& cout && endl && "端点1的坐标：";&&&&&& &&&&&& point1.Get();&&&&&&&&&&&&& cout && endl && "端点2的坐标：";&&&&&& &&&&&& point2.Get();&&&&&& }&&&&&& &&&&&& virtual ~Line(){};&private:&&&&&& Point point1;&&&&&& Point point2;};&#endif【说明】直线类的定义与实现。继承Shape的行为。#ifndef ListTest_H#define ListTest_H&#include &iostream.h&#include "List.h"#include "Circle.h"#include "Line.h"void ListTest_MObject(){&&&&&& List&Shape*&&&&&&& Shape *p1 = new C&&&&&& Shape *p2 = new L&&&&&& p1-&Input();&&&&&& p2-&Input();&&&&&& a.Insert(p1);&&&&&& a.Insert(p2);&&&&&& Shape *p = *a.Next();&&&&&& p-&Print();&&&&&& &&&&&& a.Put(NULL);&&&&&& p = *a.Next();&&&&&& p-&Print();&&&&&& &&&&&& a.Put(NULL);}#endif【说明】这是测试函数，使用方法是在含有main()的cpp文件头部加入#include “ListTest.h”，然后调用ListTest_Mobject()。这是一个简单的例子，可以看出，删除这样的链表节点需要两个步骤，先delete链表节点data域里指针所指的对象，然后才能删除链表节点。同样，析构这样链表的时候，也需要注意这个问题。不然的话，你的程序运行一次内存就少一点（可能不是这样，据说操作系统在程序中止时可以回收动态内存，但后面的结论是对的），如果是个频繁调用的函数，当运行一段时间后，你的系统就瘫痪了。所以，使用这样的链表最好是派生一个新的链表类，实现相应的操作。例如这样：class ShapeList : public List&Shape*&{public:&&&&&& BOOL SL_Remove()&&&&&& {&&&&&& &&&&&& Shape *p = *Get();&&&&&&&&&&&&& &&&&&&&&&&&&& return Remove();&&&&&& }};【闲话】不知你是不是对这样的语句Shape *p = *a.Next();&&&&&& p-&Print();不甚理解，还觉得有点罗嗦。那你试试这样的语句*a.Next()-&Print();能不能编译通过。& &2016年5月 总版技术专家分月排行榜第二
2016年10月优秀大版主2016年8月论坛优秀大版主
2015年1月 VC/MFC大版内专家分月排行榜第三
2016年10月优秀大版主2016年8月优秀大版主
2016年9月 总版技术专家分月排行榜第二
2016年5月 总版技术专家分月排行榜第二
2016年10月优秀大版主2016年8月论坛优秀大版主
2016年10月优秀大版主2016年8月优秀大版主
2016年9月 总版技术专家分月排行榜第二
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。1877人阅读
求职面试（14）
C/C++编程（29）
声明：转自/lanxuezaipiao/item/afc616caf85b
基本函数（具体代码实现见后面）
1，构造节点
&//定义节点类型
struct Node
2，分配节点
//之所以要分配节点原因是需要在分配函数中进行初始化，并且也利于判断是否分配成功。
Node* applyNode();
3，在头部增加节点
//增加节点在头部（无头结点）,返回值的原因是由于传入并非指针的引用。
Node* addNodeH(Node* Head,Node* InsertNode);
4，在尾部增加节点
//增加节点在尾部（无头结点）,返回值的原因是由于传入并非指针的引用。
Node* addNodeT(Node* Head,Node* InsertNode);
5，以升序方式增加节点
Node* addNodeSort(Node* Head,Node* InsertNode);
6，构造链表
//没有额外的表头结点。
//选择参数choose分别对应以何种方式构造链表，1为头部增加节点；2为尾部增加节点；3为升序增加节点。
Node* createList(int n,int choose);
7，打印链表
void printList(Node*Head);
8，释放链表
void freeList(Node*& Head);
9，链表节点数
int numOfNodes(Node* Head);
10，定位函数
//传入参数i表示第几个节点（从1开始），返回该节点指针
Node* locateNodeI(Node*Head,int i);
11，查找函数
//查找值为value的链表
int SearchList(Node*Head,int value);
12，删除节点
//删除位置i的节点
bool deleteNodeI(Node*&Head,int i);
13，排序函数
//冒泡排序链表，具体的做法是“狸猫换太子”，即只交换节点中的值，对链表结构不做改动。
void sortList(Node*& Head);
高级函数（具体代码实现见后面）
1.单链表反转
思路1：O(n^2).
& & & &我的做法是“狸猫换太子”，不进行改动链表结构，只首尾交换len/2次。但是在本函数中用到了定位函数，定位函数实际上是遍历了一遍整个链表，所以综合效率很低，达到O(n^2).
void reverseList(Node*Head)
思路2：O(n).
& & & &就最一般的情况而言（没有之前写的那么多辅助函数，即条件单纯为只有Head指向一个单链表）。那么可以实现O（n）效率。做法是用三个相邻的指针进行遍历，在遍历的途中，更改指针方向。当然要注意链表数目分情况，和拆链的处理。
Node* reverseList2(Node*Head)
2.找出单链表的倒数第4个元素
思路1：O(2n)
& & & & 先遍历一遍链表记录节点个数。然后定位该位置count-3，定位函数实际上也是遍历一遍，所以总效率O(n)+O(n)
bool findLast4th1(Node*Head,int &ans)
思路2：O(n)
& & & & 如果题目限制要求，仅允许遍历一遍，则可以按如下方法进行。先定义两个指针，第一个指针先走4步，然后从这时开始，第一个指针和第二个指针同时继续走，即第一个指针和第二个指针相差4步。则第二个指针到头时，第一个指针指向倒数第四个。注意要考虑链表长度。
bool findLast4th2(Node*Head,int &ans)
思路3：O(n)
& & & & 做一个数组arr[4]，让我们遍历单链表，把第1个、第5个、第9个……第4N+1个扔到arr[0]，把第2个、第6个、第10个……第4N+2个扔到arr[1]，把第3个、第7个、第11个……第4N+3个扔到arr[2]，把第4个、第8个、第12个……第4N个扔到arr[3]，这样随着单链表的遍历结束，arr中存储的就是单链表的最后4个元素，找到最后一个元素对应的arr[i]，让k=(i+1)%4，则arr[k]就是倒数第4个元素。如果不易理解，画个图就好了。注意增加的空间只需要4个，所以是常数级的。比如加到第5个节点时就会把arr[0]中的值冲掉。
bool findLast4th3(Node*Head,int &ans)
3.找出单链表的中间元素
思路1：O(2n)
& & & & &在函数的支持下，直接求整个链表的长度，然后定位中间元素。
bool getMiddleOne1(Node*Head,int&ans)
思路2：O(n)
& & & & 如果仍要求只遍历一遍。类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：
bool getMiddleOne2(Node*Head,int&ans)
4.删除无头单链表的一个节点
& & & && 注意这里的要求是无头链表，即未知Head指针。但是知道的是current指针指向该链表的某一位置。现在希望删除该指针，而不影响整个链表。即虽然不知道Head指针，但是该链还是完整的。
& & & & 首先需要明确一点，即current指针之前的链表段落是不可能知道的。这是由链表的单向性决定的。没有任何技术可以做到这一点。
& & & & 其次，删除链表某节点，该节点不能是首节点，因为首节点一旦删除，Head无法找到该链表了。
& & & & 再次，删除链表某节点，该节点不能是尾节点，因为尾节点一旦删除，则尾节点的前一节点的指针域无法置0（因为单链无法回溯）。
& & & & 所以题意解释为：删除无头单链表的一个节点（既非首节点也非尾节点）。
& & & & 解法是利用“狸猫换太子”。首先复制current指针的下一个节点的value到current节点中。然后删除current的下一节点。
void deleteNoHeadList(Node*Head,Node*Current)
& & & && & & &&
4+.增加无头单链表的一个节点，一个指针current指向单链表中的一个节点，在该节点之前增加一个节点insertNode。
& & & & &思路还是“狸猫换太子”，即在current之后增加一个节点insertNode，然后交换insertNode和current的值。
& & & & &由于在current之后增加节点这个操作在current指向首尾都可以实现。
& & & & &所以这道问题转化为：增加无头单链表的一个节点，current指针指向该链表某节点（可以为首尾），在其之前增加节点p。
void addNoHeadList(Node*Head,Node*Current,Node*insertNode)
5.两个不交叉的有序链表的合并
思路：O(len1+len2)
& & & & 合并的办法如下，首先用Node*& 方式传入两个链表的头指针Head1，Head2。用指针引用是因为最后要修改Head1和Head2均为NULL。否则可能被其他人误引用了。然后定义一个合并后的链表的头指针和尾指针Head和Tail。然后不断比较Head1和Head2的首元素，加入到新的合并的链表中。注意一点这里的加入并不是先增加申请一个节点分配，然后删除释放原来的节点。而是直接将指针指向。也就是说在合并的过程中只是指针指向改变了，完全没有申请新的内存和释放节点空间。最后如果有一个Head1或Head2的已经空了，则直接将剩余链表连接到Head即可。当然要注意很多细节。
Node* mergeTwoList(Node*& Head1,Node*& Head2)
6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。
& & & & 注意要重新定义二级单链表的结构，具体的算法是：把所有的下级单链表顺次连接。即可。程序代码略。
7.单链表交换任意两个元素（不包括表头）
& & & & & 利用“狸猫换太子”，不破坏链表结构，只交换二者Node* cur1和Node* cur2的指向的值。程序代码略。
& & & & & 其中的任意两个元素由外界给定该两个节点的指针。
8.判断单链表是否有环（6形状）？如何找到环的“起始”点？如何知道环的长度？
& & & & 注意分析题意，题意并非是说单链表完全成O形状的环，而是说单链表成6形状的环。
& & & & 首先判断是否有环：为此我们建立两个指针，从Head一起向前跑，一个步长为1，一个步长为2，用
& while(直到步长2的跑到结尾)
检查两个指针是否相等，直到找到为止。
来进行判断。
& & & & & & 原因是，在这场跑步中，结束循环有两种可能，其一是原来无环，所以2先跑到结尾，因为2比1快，二者不可能相等。其二是原来是有环的，因为这场赛跑永远没有z终点，但是在环中，由于2比1快，因而必定套圈，也即2追上了1，这在无环中是不可能出现的情况。
& & & & & &而进行计算环的长度，只要找到交汇点，然后在圈中跑一次就可以了。
int getCircleLength(Node* cross)
bool judgeCircleExists(Node* Head)
9.判断两个单链表是否相交
& & & & & & 注意这里是判断是否相交。对于判断问题来讲，相对还是比较简单的。注意单链表并非不能有重复元素。
思路1：O(len1*len2)
& & & & & & 把第一个链表的指针值逐项存在hashtable中，遍历第2个链表的每一项的指针值，如果能在第一个链表中找到，则必然相交。但是C++的STL模板中的hash不太会用。所以我使用了set集合，不过貌似set集合是使用遍历的方式来查找元素是否在集合中的，所以效率是比较低的，至少在O(len1*len2)级别。
bool judgeIntersectList1(Node* Head1,Node* Head2)
思路2：O(len1+len2)
& & & & & 把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢？从A开始遍历，如果能回到A的表头，则肯定有环。
注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。
bool judgeIntersectList2(Node* Head1,Node* Head2)
思路3：O（len1+len2）
& & & & &如果两个链表的末尾元素相同（指针相同，即为同一个元素，而非值相等），则必相交。
bool judgeIntersectList3(Node* Head1,Node* Head2)
10.两个单链表相交，计算相交点
& & & & &分别遍历两个单链表，计算出它们的长度M和N，假设M比N大，则长度M的链表先前进M-N，然后两个链表同时以步长1前进，前进的同时比较当前的元素，如果相同，则必是交点。
Node* getIntersectPoint(Node* Head1,Node* Head2)
& & & & &将指针p1,p2定位到两个链表的尾部，然后同时将两个指针前移（不可以，因为是单向链表）
11.用链表模拟大整数加法运算
&&&&&&& 对于高精度大数计算，没有数组那么高效，具体数组的做法参见OJ高精度，链表的好处是可以定义节点，其中包含指数次数和值两部分，比如20001可以表示为(2,4)-&(1,0)-&NULL其中2表示值，4表示10的4次方。这样的话如果数属于稀疏型的则以较少的空间保存了值。具体程序略。
12.单链表排序
&&&&&&&& 参见基本函数13：//冒泡排序链表，具体的做法是“狸猫换太子”，即只交换节点中的值，对链表结构不做改动。
void sortList(Node*& Head);
13.删除单链表中重复的元素
&&&&&&&&&用Hashtable辅助，遍历一遍单链表就能搞定。同高级函数9的原因，我不太会使用C++STL中的hash。而如果使用set集合来存储链表中的所有的值，实际上效率和每次重新遍历单链表是一样的。“用了c++标准库中的set来保存访问过的元素，所以很方便的就可以判断当前节点是否在set集合中，直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。”我不太清楚STL中set集合的实现方式，如果是基于类似hash结构的话，那自然效率O(1),而如果是数组的话，实际在遍历一遍，所以效率O(n)。不过貌似后者的可能性大一些。
void DeleteDuplexElements(Node*Head);
基本函数代码：
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2，分配节点
//分配节点
//将分配内存和初始化该节点放在一个函数中
Node* applyNode()
&Node* newN
&if((newNode=(Node*)malloc(sizeof(Node)))==NULL)
&&cout&&&分配内存失败！&&&
&&::exit(0);
&//建立该节点信息：
&cout&&&请输入本节点值：&&&
&cin&&newNode-&
&newNode-&next=NULL;
&return newN
3，在头部增加节点
//在表头增加节点
//在头指针所指向的链表中增加一个节点,插入头部
//这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&
Node* addNodeH(Node* Head,Node* InsertNode)
&if(Head==NULL)
&&Head=InsertN
&&InsertNode-&next=H
&&Head=InsertN
4，在尾部增加节点
//在表尾增加节点
//在头指针所指向的链表中增加一个节点,插入尾部
//这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&
Node* addNodeT(Node* Head,Node* InsertNode)
&if(Head==NULL)
&&Head=InsertN
&&Node* p=H
&&while(p-&next!=NULL)
&&p-&next=InsertN
5，以升序方式增加节点
//以升序增加节点
//这里必须要返回Node*来进行更新，因为传入的Head是Node*类型，而非Node*&
Node* addNodeSort(Node* Head,Node* InsertNode)
&if(Head==NULL)
&&Head=InsertN
&&Node* p=H
&&//注意，这里把(p-&value)&(InsertNode-&value)放在p-&next!=NULL前面是有原因的，这是避免为了考虑在Head-&[4]加入[1]的情况
&&while((p-&value)&(InsertNode-&value)&&p-&next!=NULL)
&&if((p-&value)&=(InsertNode-&value))//因为（(p-&value)&=(InsertNode-&value)）而退出！表示在p前增加节点（狸猫换太子）
&&&//先在p后增加节点
&&&InsertNode-&next=p-&
&&&p-&next=InsertN
&&&//再交换p和InsertNode的值
&&&swap(p-&value,InsertNode-&value);
&&else//因为（p-&next==NULL）而退出！表示在尾增加节点
&&&p-&next=InsertN
6，构造链表
//建立n个节点的链表 choose=1,在表头加入，choose=2在表尾加入,choose=3按value值升序加入
Node* createList(int n,int choose)
&Node *Head=NULL,*p=NULL;
&for(int i=0;i&n;i++)
&&p=applyNode();
&&if(choose==1)
&&&Head=addNodeH(Head,p);
&&else if(choose==2)
&&&Head=addNodeT(Head,p);
&&else if(choose==3)
&&&Head=addNodeSort(Head,p);
7，打印链表
//遍历链表并输出
void printList(Node*Head)
&while(p!=NULL)
&&cout&&p-&value&&&-&&;
&cout&&&NULL&&&
8，释放链表
//释放链表
void freeList(Node*& Head)
&Node* tmp=H
&while(tmp!=NULL)
&&Head=Head-&
&&free(tmp);
&Head=NULL;&
9，链表节点数
//数节点个数
int numOfNodes(Node* Head)
&int count=0;
&while(Head!=NULL)
&&count++;
&&Head=Head-&
10，定位函数
//定位第i个节点，i从1开始
Node* locateNodeI(Node*Head,int i)
&//cout&&&定位&&&i&&&位置&&&
&Node* pos=NULL;
&int count=numOfNodes(Head);
&if(i&=0||i&count)
&&cout&&&定位越界！&&&
&&for(int j=1;j&i;j++)
&&&pos=pos-&
11，查找函数
//查找值value并返回第一个出现该值的位置，如果需要引用其指针，可以再locate该位置
int SearchList(Node*Head,int value)
&Node* p=H
&int pos=0;
&bool find=
&while(p!=NULL)
&&pos++;
&&if(p-&value==value)
&&return -1;
12，删除节点
//删除某位置i的节点
bool deleteNodeI(Node*&Head,int i)
&Node* p=locateNodeI(Head,i);
&if(p==NULL)
&&if(p==Head)//说明p是头节点。
&&&Head=p-&
&&&free(p);
&&&Node* prep=locateNodeI(Head,i-1);//定位前一个,必定存在&
&&&prep-&next=p-&
&&&free(p);
13，排序函数
//链表排序
//排序的方法是不破坏结构，有“狸猫换太子”的意思，只进行value的交换，不破坏链表结构
void sortList(Node*& Head)
&int count=numOfNodes(Head);
&if(count==0||count==1)
&//冒泡排序
&for(int i=2;i&=i++)
&&exchange=
&&for(int j=j&=i;j--)
&&&Node* p1=locateNodeI(Head,j);
&&&Node* p2=locateNodeI(Head,j-1);
&&&if(p1-&value&p2-&value)
&&&&exchange=
&&&&swap(p1-&value,p2-&value);
&&if(!exchange)
高级函数代码：
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1.单链表反转1
//单链表反转(O(n^2))
void reverseList(Node*Head)
&int count=numOfNodes(Head);
&//“狸猫换太子”，首尾交换
&for(int i=1;i&=count/2;i++)
&&Node* p1=locateNodeI(Head,i);
&&Node* p2=locateNodeI(Head,count+1-i);
&&swap(p1-&value,p2-&value);
1.单链表反转2
//单链表反转（O(n)）
Node* reverseList2(Node*Head)
&if(Head==NULL||Head-&next==NULL)//空链和单节点
&&return H
&Node* p1=H
&Node* p2=Head-&
&Node* p3=Head-&next-&
&if(p3==NULL)//只有两个节点
&&p1-&next=NULL;
&&p2-&next=p1;
&&Head=p2;
&&return H
&else//至少三个节点
&&p1-&next=NULL;
&&while(p3!=NULL)
&&&p2-&next=p1;
&&&p3=p3-&
&&p2-&next=p1;
&&Head=p2;
&&return H
2.找出单链表的倒数第4个元素1
//查找倒数第四个元素,传入ans中 O(2N)
bool findLast4th1(Node*Head,int &ans)
&//先确定节点个数：
&int count=numOfNodes(Head);
&//定位count-4
&Node* p=locateNodeI(Head,count-3);
&if(p!=NULL)
2.找出单链表的倒数第4个元素2
//查找倒数第四个元素,传入ans中 O(N),只遍历一遍
bool findLast4th2(Node*Head,int &ans)
&Node* p1=H
&Node* p2=H
&//p1先走4步。
&for(int i=0;i&4;i++)
&&if(p1!=NULL)
&&&p1=p1-&
&&&//肯定链表长度不够
&//同步移动
&while(p1!=NULL)
2.找出单链表的倒数第4个元素3
//查找倒数第四个元素,传入ans中 O(N)
bool findLast4th3(Node*Head,int &ans)
&int arr[4];
&Node* p=H
&int count=0;
&while(p!=NULL)
&&arr[i]=p-&
&&i=(i+1)%4;
&&count++;
&if(count&4)
&&ans=arr[i];
3.找出单链表的中间元素1
//获取中间元素O(2n)
bool getMiddleOne1(Node*Head,int&ans)
&int count=numOfNodes(Head);
&if(count==0)
&&Node* p=locateNodeI(Head,(count+1)/2);
3.找出单链表的中间元素2
//获取中间元素O(n)
//类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：
bool getMiddleOne2(Node*Head,int&ans)
&if(Head==NULL)//空链表
&&Node*first=H
&&Node*second=Head-&
&&while(second!=NULL&&second-&next!=NULL)
&&&first=first-&
&&&second=second-&
&&&second=second-&
&&ans=first-&
4.删除无头单链表的一个节点
//删除无头单链表的非首尾节点&狸猫换太子&;
void deleteNoHeadList(Node*Head,Node*Current)
&Node* p=Current-&
&//一定是非首尾节点,否则会出错
&Current-&value=Current-&next-&
&Current-&next=Current-&next-&
4+.增加无头单链表的一个节点，一个指针current指向单链表中的一个节点，在该节点之前增加一个节点insertNode。
//增加无头单链表的一个节点，current指针指向该链表某节点（可以为首尾），在其之前增加节点insertNode。
void addNoHeadList(Node*Head,Node*Current,Node*insertNode)
&insertNode-&next=Current-&
&Current-&next=insertN
&swap(Current-&value,insertNode-&value);
5.两个不交叉的有序链表的合并
//合并两个有序的链表
Node* mergeTwoList(Node*& Head1,Node*& Head2)
&Node* Head=NULL;//合并后的链表
&Node* Tail=NULL;//合并后链表的尾指针
&//p1,p2遍历两个链表
&Node* p1=Head1;
&Node* p2=Head2;
&while(!(p1==NULL||p2==NULL))
&&if(p1-&value&=p2-&value)
&&&if(Head==NULL)//第一个节点
&&&&Head=p1;
&&&&Tail=H
&&&&Tail-&next=p1;
&&&&Tail=Tail-&
&&&p1=p1-&
&&&if(Head==NULL)//第一个节点
&&&&Head=p2;
&&&&Tail=H
&&&&Tail-&next=p2;
&&&&Tail=Tail-&
&&&p2=p2-&
&if(p1!=NULL)
&&if(Head!=NULL)
&&&Tail-&next=p1;
&&&Head=p1;
&else if(p2!=NULL)
&&if(Head!=NULL)
&&&Tail-&next=p2;
&&&Head=p2;
&Head1=NULL;
&Head2=NULL;
8.判断单链表是否有环（6形状）？如何找到环的“起始”点？如何知道环的长度？1
//计算单链表成环，环的长度,输入的参数为成环的交汇点。
int getCircleLength(Node* cross)
&int len=1;
&while(p-&next!=cross)//千万不能写作p-&next!=p
&&len++;
8.判断单链表是否有环（6形状）？如何找到环的“起始”点？如何知道环的长度？2
//判断单链表是否有环,并且返回环的长度
bool judgeCircleExists(Node* Head,int &len)
&if(Head==NULL)//空链
&else if(Head-&next==Head)//1个节点且成环
&else if(Head-&next==NULL)//1个节点不成环
&//至少两个节点情形
&//初始化跑步机
&Node* p1=H//跑步者1号,跑到第1个节点
&Node* p2=Head-&//跑步者2号，跑到第2个节点
&while(p2!=NULL&&p2-&next!=NULL)//利用了&&短路
&&p2=p2-&next-&
&&if(p1==p2)
&&&//此时p1（p2）即为交汇点
&&&len=getCircleLength(p1);
9.判断两个单链表是否相交1
//判断两个单链表是否相交（Y型）
bool& judgeIntersectList1(Node* Head1,Node* Head2)
&set&Node*&s;
&Node* p1=Head1;
&Node* p2=Head2;
&while(p1!=NULL)
&&s.insert(p1);
&while(p2!=NULL)
&&if(s.find(p2)!=s.end())
&&&s.clear();
&s.clear();
9.判断两个单链表是否相交2
//判断两个单链表是否相交（Y型）
bool& judgeIntersectList2(Node* Head1,Node* Head2)
&if(Head1==NULL||Head2==NULL)
&Node* p1=Head1;
&Node* p2=Head2;
&//先找到链表2的末尾,由p2指向
&while(p2-&next!=NULL)
&//将链表1的表头与链表2的表尾连接
&p2-&next=p1;
&//遍历链表1，如果回到了链表1表头，则相交
&while(p1!=NULL)
&&if(p1-&next==Head1)
&&&//记得恢复原状：
&&&p2-&next=NULL;
&//记得恢复原状：
&&&& p2-&next=NULL;
9.判断两个单链表是否相交3
//判断两个单链表是否相交（Y型）
bool& judgeIntersectList3(Node* Head1,Node* Head2)
&if(Head1==NULL||Head2==NULL)
&Node* p1=Head1;
&Node* p2=Head2;
&//p1与p2记录两链表的尾指针
&while(p1-&next!=NULL)
&while(p2-&next!=NULL)
&if(p1==p2)
10.两个单链表相交，计算相交点
//两链表相交，计算相交点：
Node* getIntersectPoint(Node* Head1,Node* Head2)
&int len1=numOfNodes(Head1);
&int len2=numOfNodes(Head2);
&int initMove=abs(len1-len2);
&Node* p1=Head1;
&Node* p2=Head2;
&if(len1&len2)
&&for(int i=0;i&initMi++)
&&&p1=p1-&
&&for(int i=0;i&initMi++)
&&&p2=p2-&
&while(p1!=NULL&&p2!=NULL)
&&if(p1==p2)
&&&return p1;
&return NULL;
12.单链表排序
//链表排序
//排序的方法是不破坏结构，有“狸猫换太子”的意思，只进行value的交换，不破坏链表结构
void sortList(Node*& Head)
&int count=numOfNodes(Head);
&if(count==0||count==1)
&//冒泡排序
&for(int i=2;i&=i++)
&&exchange=
&&for(int j=j&=i;j--)
&&&Node* p1=locateNodeI(Head,j);
&&&Node* p2=locateNodeI(Head,j-1);
&&&if(p1-&value&p2-&value)
&&&&exchange=
&&&&swap(p1-&value,p2-&value);
&&if(!exchange)
13.删除单链表中重复的元素
//删除单链表中的重复元素：使用set集合来实现：
void DeleteDuplexElements(Node*Head)
&if(Head==NULL||Head-&next==NULL)//链表为空或者只有一个元素
&//以下至少两个元素
&set&int&s;
&Node* p1=H
&Node* p2=Head-&
&s.clear();
&s.insert(p1-&value);
&while(p2!=NULL)//要删除的不可能是链表头,因为如果是链表头，则集合还为空。
&&if(s.find(p2-&value)==s.end())//没有
&& s.insert(p2-&value);
&& p2=p2-&
&& p1=p1-&
&&else//已经有，则要删除该节点
&&&//不可能是链表头
&&&//如果是链表尾
&&&if(p2-&next==NULL)
&&&&p1-&next=NULL;
&&&&free(p2);
&&&&p2=NULL;
&&&&p1-&next=p2-&
&&&&free(p2);
&&&&p2=p1-&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
以前的博客，虽已不再更新，但某些文章也值得参考滴：
生活、读书、感悟等非技术性文章，请移步至我的简书博客：
收藏了很多读书和电影条目，基本上都有自己的评鉴语：
微信学习公众平台-媛媛推荐
微信号：programer-idea
名称：程序媛想事儿
访问：607891次
积分：8922
积分：8922
排名：第1704名
原创：123篇
转载：14篇
评论：1050条
阅读：52645
文章：16篇
阅读：87368
阅读：36570
(1)(1)(1)(2)(3)(9)(5)(17)(4)(8)(4)(4)(5)(1)(7)(4)(22)(14)(10)(5)(11)(2)(1)}