1. 单链表反转
思路1：O(n^2).
“狸猫换太子”，不进行改动链表结构，只首尾交换len/2次。但是在本函数中用到了定位函数，定位函数实际上是遍历了一遍整个链表，所以综合效率很低，达到O(n^2).
//单链表反转(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);
}
}
思路2：O(n).
就最一般的情况而言（没有之前写的辅助函数，即条件单纯为只有Head指向一个单链表）。可以实现O（n）效率。
做法是用三个相邻的指针进行遍历，在遍历的途中，更改指针方向。当然要注意链表数目分情况，和拆链的处理。
//单链表反转（O(n)）
Node* reverseList2(Node* Head)
{
if(Head==NULL || Head->next==NULL) //空链和单节点
return Head;
Node* p1 = Head;
Node* p2 = Head->next;
Node* p3 = Head->next->next;
if(p3==NULL){ //只有两个节点
p1->next = NULL;
p2->next = p1;
Head = p2;
return Head;
}
else{ //至少三个节点
p1->next = NULL;
while(p3!=NULL){
p2->next = p1;
//三个指针依次向后移一位
p1=p2;
p2=p3;
p3=p3->next;
}
p2->next = p1;
Head = p2;
return Head;
}
}
2. 找单链表倒数第4个元素
思路1：O(2N)
//查找倒数第四个元素,传入ans中 O(2N)
bool findLast4th1(Node* Head, int& ans)
{
//先确定节点个数：
int count = numOfNodes(Head);
//定位count-4
Node* p = locateNodeI(Head, count-3);
if(p!=NULL){
ans = p->value;
return true;
}
else{
return false;
}
}
思路2：O(N)
//查找倒数第四个元素,传入ans中 O(N),只遍历一遍
bool findLast4th2(Node* Head, int& ans)
{
Node* p1 = Head;
Node* p2 = Head;
//p1先走4步。
for(int i=0;i<4;i++){
if(p1!=NULL){
p1=p1->next;
}
else{
return false; //肯定链表长度不够
}
}
//同步移动
while(p1!=NULL){
p1 = p1->next;
p2 = p2->next;
}
ans=p2->value;
return true;
}
思路3：O(N)
//查找倒数第四个元素,传入ans中 O(N)
bool findLast4th3(Node* Head, int& ans)
{
int arr[4];
Node* p=Head;
int i=0;
int count=0;
while(p!=NULL){
arr[i]=p->value;
p = p->next;
i = (i+1)%4; //周期为4，则 i+1 和 i-3 是同一个位置
count++;
}
if(count<4){
return false;
}
else{
ans=arr[i];
return true;
}
}
3. 找单链表的中间元素
思路1：O(2n)
//获取中间元素O(2n)
bool getMiddleOne1(Node* Head, int& ans)
{
int count = numOfNodes(Head);
if(count==0){
return false;
}
else{
Node* p = locateNodeI(Head,(count+1)/2);
ans = p->value;
return true;
}
}
思路2：O(n)
//获取中间元素O(n)
//使用两个指针first和second，first每次走一步，second每次走两步：
bool getMiddleOne2(Node* Head, int& ans)
{
if(Head==NULL)//空链表
return false;
else{
Node* first=Head;
Node* second=Head->next;
while(second!=NULL && second->next!=NULL){
first = first->next;
second = second->next;
second = second->next;
}
ans = first->value;
return true;
}
}
4. 增加删除无头单链表的一个节点
增加无头单链表的一个节点
//增加无头单链表的一个节点，current指针指向该链表某节点（可以为首尾），在其之前增加节点insertNode
void addNoHeadList(Node* Head, Node* Current, Node* insertNode)
{
insertNode->next = Current->next;
Current->next = insertNode;
swap(Current->value, insertNode->value);
}
删除无头单链表的一个节点
//删除无头单链表的非首尾节点："狸猫换太子";
void deleteNoHeadList(Node* Head, Node* Current)
{
Node* p = Current->next;
//一定是非首尾节点，否则会出错
Current->value = Current->next->value;
Current->next = Current->next->next;
free(p);
}
5. 两个不交叉的有序链表的合并
思路：O(len1+len2)
1）用 Node*& 方式传入两个链表的头指针Head1，Head2。
//用指针引用是因为最后要将Head1和Head2修改为NULL
2）定义一个合并后的链表的头指针和尾指针Head和Tail。
3）不断比较Head1和Head2的首元素，加入到新的合并的链表中。
4）注意：这里的加入并不是先增加申请一个节点分配，然后删除释放原来的节点。而是直接将指针指向。也就是说在合并的过程中只是指针指向改变了，完全没有申请新的内存和释放节点空间。最后如果有一个Head1或Head2的已经空了，则直接将剩余链表连接到Head即可。
//合并两个有序链表
Node* mergeTwoList(Node*& Head1, Node*& Head2)
{
Node* Head = NULL; //合并后的链表
Node* Tail = NULL; //合并后链表的尾指针
//p1,p2遍历两个链表
Node* p1 = Head1;
Node* p2 = Head2;
while(p1 && p2){
if(p1->value <= p2->value){
if(Head==NULL){ //p1所指作合并后的第一个节点
Head=p1;
Tail=Head;
}
else{
Tail->next=p1;
Tail=Tail->next;
}
p1=p1->next;
}
else{
if(Head==NULL){ //p2所指作合并后的第一个节点
Head=p2;
Tail=Head;
}
else{
Tail->next=p2;
Tail=Tail->next;
}
p2=p2->next;
}
}
//p1或p2遍历完链表，连接为遍历完的链表的剩余结点
if(p1){
if(Head!=NULL)
Tail->next=p1;
else
Head=p1;
}
if(p2){
if(Head!=NULL)
Tail->next=p2;
else
Head=p2;
}
Head1=NULL;
Head2=NULL;
return Head;
}
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)
//单链表成环，计算环的长度（输入的参数为成环的交汇点）
int getCircleLength(Node* cross)
{
int len=1;
Node* p=cross;
while(p->next!=cross){ //不能写作 p->next!=p
len++;
p=p->next;
}
return len;
}
//判断单链表是否有环，并且返回环的长度
bool judgeCircleExists(Node* Head,int &len)
{
if(Head==NULL) //空链
return false;
else if(Head->next==Head) //1个节点且成环
return true;
else if(Head->next==NULL) //1个节点不成环
return false;
//至少两个节点情形
//初始化跑步机
Node* p1=Head; //跑步者1号，跑到第1个节点
Node* p2=Head->next; //跑步者2号，跑到第2个节点
while(p2!=NULL&&p2->next!=NULL){ //利用了&&短路
p1=p1->next;
p2=p2->next->next;
if(p1==p2){
//此时p1（p2）即为交汇点
len=getCircleLength(p1);
return true;
}
}
return false;
}
9.判断两个单链表是否相交
注意这里是判断是否相交。对于判断问题来讲，相对还是比较简单的。注意单链表并非不能有重复元素。
思路1：O(len1*len2)
把第一个链表的指针值逐项存在hashtable中，遍历第2个链表的每一项的指针值，如果能在第一个链表中找到，则必然相交。但是C++的STL模板中的hash不太会用。所以我使用了set集合，不过貌似set集合是使用遍历的方式来查找元素是否在集合中的，所以效率是比较低的，至少在O(len1*len2)级别。
bool judgeIntersectList1(Node* Head1,Node* Head2)
//判断两个单链表是否相交（Y型）
bool judgeIntersectList1(Node* Head1,Node* Head2)
{
set<Node*>s;
Node* p1=Head1;
Node* p2=Head2;
while(p1!=NULL){
s.insert(p1);
p1=p1->next;
}
while(p2!=NULL){
if(s.find(p2)!=s.end()){
s.clear();
return true;
}
p2=p2->next;
}
s.clear();
return false;
}
思路2：O(len1+len2)
把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢？从A开始遍历，如果能回到A的表头，则肯定有环。
注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。
bool judgeIntersectList2(Node* Head1,Node* Head2)
//判断两个单链表是否相交（Y型）
bool judgeIntersectList2(Node* Head1,Node* Head2)
{
if(Head1==NULL||Head2==NULL){
return false;
}
Node* p1=Head1;
Node* p2=Head2;
while(p2->next!=NULL){ //先找到链表2的末尾，由p2指向
p2=p2->next;
}
p2->next=p1; //将链表1的表头与链表2的表尾连接
while(p1!=NULL){ //遍历链表1，如果回到了链表1表头，则相交
if(p1->next==Head1){
p2->next=NULL; //恢复原状
return true;
}
p1=p1->next;
}
p2->next=NULL; //恢复原状
return false;
}
思路3：O（len1+len2）
如果两个链表的末尾元素相同（指针相同，即为同一个元素，而非值相等），则必相交。
bool judgeIntersectList3(Node* Head1,Node* Head2)
//判断两个单链表是否相交（Y型）
bool judgeIntersectList3(Node* Head1,Node* Head2)
{
if(Head1==NULL || Head2==NULL){
return false;
}
Node* p1=Head1;
Node* p2=Head2;
while(p1->next!=NULL) //p1与p2记录两链表的尾指针
p1=p1->next;
while(p2->next!=NULL)
p2=p2->next;
if(p1==p2){
return true;
}
return false;
}
10.两个单链表相交，计算相交点
思路1：
分别遍历两个单链表，计算出它们的长度M和N，假设M比N大，则长度M的链表先前进M-N，然后两个链表同时以步长1前进，前进的同时比较当前的元素，如果相同，则必是交点。
Node* getIntersectPoint(Node* Head1,Node* Head2)
//两链表相交，计算相交点
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<initMove; i++)
p1=p1->next;
}
else{
for(int i=0; i<initMove; i++)
p2=p2->next;
}
while(p1!=NULL && p2!=NULL){
if(p1==p2){
return p1;
}
p1=p1->next;
p2=p2->next;
}
return NULL;
}
思路2：
将指针p1,p2定位到两个链表的尾部，然后同时将两个指针前移（不可以，因为是单向链表）
12.单链表排序
思路：
参见基本函数13：//冒泡排序链表，具体的做法是“狸猫换太子”，即只交换节点中的值，对链表结构不做改动。
void sortList(Node*& Head);
//链表排序
//排序的方法是不破坏结构，有“狸猫换太子”的意思，只进行value的交换，不破坏链表结构
void sortList(Node*& Head)
{
int count=numOfNodes(Head);
if(count==0||count==1){
return ;
}
//冒泡排序
bool exchange;
for(int i=2;i<=count;i++){
exchange=false;
for(int j=count;j>=i;j--){
Node* p1=locateNodeI(Head,j);
Node* p2=locateNodeI(Head,j-1);
if(p1->value<p2->value){
exchange=true;
swap(p1->value,p2->value);
}
}
if(!exchange)
break;
}
}
13.删除单链表中重复的元素
思路：
用Hashtable辅助，遍历一遍单链表就能搞定。同高级函数9的原因，我不太会使用C++STL中的hash。而如果使用set集合来存储链表中的所有的值，实际上效率和每次重新遍历单链表是一样的。“用了c++标准库中的set来保存访问过的元素，所以很方便的就可以判断当前节点是否在set集合中，直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。”我不太清楚STL中set集合的实现方式，如果是基于类似hash结构的话，那自然效率O(1),而如果是数组的话，实际在遍历一遍，所以效率O(n)。不过貌似后者的可能性大一些。
void DeleteDuplexElements(Node*Head);
//删除单链表中的重复元素（使用set集合来实现）
void DeleteDuplexElements(Node*Head)
{
if(Head==NULL||Head->next==NULL){ //链表为空或者只有一个元素
return ;
}
//以下至少有两个元素
set<int>s;
Node* p1=Head;
Node* p2=Head->next;
s.clear();
s.insert(p1->value);
while(p2!=NULL){ //要删除的不可能是链表头，因为如果是链表头，则集合还为空
if(s.find( p2->value)==s.end() ){ //没有
s.insert(p2->value);
p2=p2->next;
p1=p1->next;
}
else{ //已经有，则要删除该节点
if(p2->next==NULL){ //如果是链表尾
p1->next=NULL;
free(p2);
p2=NULL;
}
else{
p1->next=p2->next;
free(p2);
p2=p1->next;
}
}
}
}