http://blog.csdn.net/lanxuezaipiao/article/details/22100021

基本函數（具體代碼實現見后面）

1，構造節點

?//定義節點類型
struct Node
{
??? int value;
??? Node*next;
};

?

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.兩個單鏈表相交，計算相交點

思路1：

? ? ? ? ?分別遍歷兩個單鏈表，計算出它們的長度M和N，假設M比N大，則長度M的鏈表先前進M-N，然后兩個鏈表同時以步長1前進，前進的同時比較當前的元素，如果相同，則必是交點。
Node* getIntersectPoint(Node* Head1,Node* Head2)

思路2：

? ? ? ? ?將指針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* newNode;
?if((newNode=(Node*)malloc(sizeof(Node)))==NULL)
?{
??cout<<"分配內存失敗！"<<endl;
??::exit(0);
?}
?//建立該節點信息：
?cout<<"請輸入本節點值："<<endl;
?cin>>newNode->value;
?newNode->next=NULL;
?return newNode;
}

3，在頭部增加節點

//在表頭增加節點
//在頭指針所指向的鏈表中增加一個節點,插入頭部
//這里必須要返回Node*來進行更新，因為傳入的Head是Node*類型，而非Node*&
Node* addNodeH(Node* Head,Node* InsertNode)
{
?if(Head==NULL)
?{
??Head=InsertNode;
?}
?else
?{
??InsertNode->next=Head;
??Head=InsertNode;
?}
?return Head;
}

4，在尾部增加節點

//在表尾增加節點
//在頭指針所指向的鏈表中增加一個節點,插入尾部
//這里必須要返回Node*來進行更新，因為傳入的Head是Node*類型，而非Node*&
Node* addNodeT(Node* Head,Node* InsertNode)
{
?if(Head==NULL)
?{
??Head=InsertNode;
?}
?else
?{
??Node* p=Head;
??while(p->next!=NULL)
??{
???p=p->next;
??}
??p->next=InsertNode;
?}
?return Head;
}

5，以升序方式增加節點

//以升序增加節點
//這里必須要返回Node*來進行更新，因為傳入的Head是Node*類型，而非Node*&
Node* addNodeSort(Node* Head,Node* InsertNode)
{
?if(Head==NULL)
?{
??Head=InsertNode;
?}
?else
?{
??Node* p=Head;
??//注意，這里把(p->value)<(InsertNode->value)放在p->next!=NULL前面是有原因的，這是避免為了考慮在Head->[4]加入[1]的情況
??while((p->value)<(InsertNode->value)&&p->next!=NULL)
??{
???p=p->next;
??}
??if((p->value)>=(InsertNode->value))//因為（(p->value)>=(InsertNode->value)）而退出！表示在p前增加節點（貍貓換太子）
??{
???//先在p后增加節點
???InsertNode->next=p->next;
???p->next=InsertNode;
???//再交換p和InsertNode的值
???swap(p->value,InsertNode->value);
??}
??else//因為（p->next==NULL）而退出！表示在尾增加節點
??{
???p->next=InsertNode;
??}

?}
?return Head;
}

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);
??}
?}
?return Head;
}

7，打印鏈表
//遍歷鏈表并輸出
void printList(Node*Head)
{
?Node*p=Head;
?while(p!=NULL)
?{
??cout<<p->value<<"->";
??p=p->next;
?}
?cout<<"NULL"<<endl;
}

8，釋放鏈表

//釋放鏈表
void freeList(Node*& Head)
{
?Node* tmp=Head;
?while(tmp!=NULL)
?{
??Head=Head->next;
??free(tmp);
??tmp=Head;
?}
?Head=NULL;?
}

9，鏈表節點數
//數節點個數
int numOfNodes(Node* Head)
{
?int count=0;
?while(Head!=NULL)
?{
??count++;
??Head=Head->next;
?}
?return count;
}

10，定位函數
//定位第i個節點，i從1開始
Node* locateNodeI(Node*Head,int i)
{
?//cout<<"定位"<<i<<"位置"<<endl;
?Node* pos=NULL;
?int count=numOfNodes(Head);
?if(i<=0||i>count)
?{
??cout<<"定位越界！"<<endl;
?}
?else?
?{
??pos=Head;
??for(int j=1;j<i;j++)
??{
???pos=pos->next;
??}
?}

?return pos;
}

11，查找函數
//查找值value并返回第一個出現該值的位置，如果需要引用其指針，可以再locate該位置
int SearchList(Node*Head,int value)
{
?Node* p=Head;
?int pos=0;
?bool find=false;
?while(p!=NULL)
?{
??pos++;
??if(p->value==value)
??{
???find=true;
???break;
??}
??p=p->next;
?}
?if(find)
??return pos;
?else?
??return -1;

}

12，刪除節點
//刪除某位置i的節點
bool deleteNodeI(Node*&Head,int i)
{
?Node* p=locateNodeI(Head,i);
?if(p==NULL)
?{
??return false;
?}
?else
?{
??if(p==Head)//說明p是頭節點。
??{
???Head=p->next;
???free(p);
??}
??else
??{
???Node* prep=locateNodeI(Head,i-1);//定位前一個,必定存在?
???prep->next=p->next;
???free(p);
??}
??return true;
?}
}

13，排序函數

//鏈表排序
//排序的方法是不破壞結構，有“貍貓換太子”的意思，只進行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;
?}
}

高級函數代碼：

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

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 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

//查找倒數第四個元素,傳入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.找出單鏈表的倒數第4個元素2

//查找倒數第四個元素,傳入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;

}

2.找出單鏈表的倒數第4個元素3

//查找倒數第四個元素,傳入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;
??count++;
?}
?if(count<4)
?{
??return false;
?}
?else
?{
??ans=arr[i];
??return true;
?}
}

3.找出單鏈表的中間元素1

//獲取中間元素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;
?}

}

3.找出單鏈表的中間元素2

//獲取中間元素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.刪除無頭單鏈表的一個節點

//刪除無頭單鏈表的非首尾節點"貍貓換太子";
void deleteNoHeadList(Node*Head,Node*Current)
{
?Node* p=Current->next;
?//一定是非首尾節點,否則會出錯
?Current->value=Current->next->value;
?Current->next=Current->next->next;
?free(p);
}

4+.增加無頭單鏈表的一個節點，一個指針current指向單鏈表中的一個節點，在該節點之前增加一個節點insertNode。
//增加無頭單鏈表的一個節點，current指針指向該鏈表某節點（可以為首尾），在其之前增加節點insertNode。
void addNoHeadList(Node*Head,Node*Current,Node*insertNode)
{
?insertNode->next=Current->next;
?Current->next=insertNode;
?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=Head;
???}
???else
???{
????Tail->next=p1;
????Tail=Tail->next;
???}
???p1=p1->next;
??}
??else
??{
???if(Head==NULL)//第一個節點
???{
????Head=p2;
????Tail=Head;
???}
???else
???{
????Tail->next=p2;
????Tail=Tail->next;
???}
???p2=p2->next;
??}
?}
?if(p1!=NULL)
?{
??if(Head!=NULL)
??{
???Tail->next=p1;
??}
??else
??{
???Head=p1;
??}
?}
?else if(p2!=NULL)
?{
??if(Head!=NULL)
??{
???Tail->next=p2;
??}
??else
??{
???Head=p2;
??}

?}
?Head1=NULL;
?Head2=NULL;
?return Head;
}

8.判斷單鏈表是否有環（6形狀）？如何找到環的“起始”點？如何知道環的長度？1
//計算單鏈表成環，環的長度,輸入的參數為成環的交匯點。
int getCircleLength(Node* cross)
{
?int len=1;
?Node* p=cross;
?while(p->next!=cross)//千萬不能寫作p->next!=p
?{
??len++;
??p=p->next;
?}
?return len;
}

8.判斷單鏈表是否有環（6形狀）？如何找到環的“起始”點？如何知道環的長度？2

//判斷單鏈表是否有環,并且返回環的長度
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
//判斷兩個單鏈表是否相交（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;
}

9.判斷兩個單鏈表是否相交2

//判斷兩個單鏈表是否相交（Y型）
bool? judgeIntersectList2(Node* Head1,Node* Head2)
{
?if(Head1==NULL||Head2==NULL)
?{
??return false;
?}

?Node* p1=Head1;
?Node* p2=Head2;
?//先找到鏈表2的末尾,由p2指向
?while(p2->next!=NULL)
?{
??p2=p2->next;
?}
?//將鏈表1的表頭與鏈表2的表尾連接
?p2->next=p1;
?//遍歷鏈表1，如果回到了鏈表1表頭，則相交
?while(p1!=NULL)
?{
??if(p1->next==Head1)
??{
???//記得恢復原狀：
???p2->next=NULL;
???return true;
??}
??p1=p1->next;
?}
?//記得恢復原狀：
???? p2->next=NULL;
?return false;
}

9.判斷兩個單鏈表是否相交3

//判斷兩個單鏈表是否相交（Y型）
bool? judgeIntersectList3(Node* Head1,Node* Head2)
{
?if(Head1==NULL||Head2==NULL)
?{
??return false;
?}

?Node* p1=Head1;
?Node* p2=Head2;
?//p1與p2記錄兩鏈表的尾指針
?while(p1->next!=NULL)
?{
??p1=p1->next;
?}
?while(p2->next!=NULL)
?{
??p2=p2->next;
?}
?if(p1==p2)
?{
??return true;
?}
?return false;
}

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<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;
}

12.單鏈表排序

//鏈表排序
//排序的方法是不破壞結構，有“貍貓換太子”的意思，只進行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.刪除單鏈表中重復的元素

//刪除單鏈表中的重復元素：使用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;
???}
??}
?}
}

總結

以上是生活随笔為你收集整理的链表相关的算法题大汇总 — 数据结构之链表奇思妙想的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。