1.判斷兩個(gè)鏈表是否相交

????兩個(gè)鏈表是否相交可分為以下幾種情況
????（1）兩個(gè)鏈表都不帶環(huán)，此時(shí)兩個(gè)鏈表所對(duì)應(yīng)的最后一個(gè)節(jié)點(diǎn)是相等的
????（2）兩個(gè)鏈表一個(gè)帶環(huán)，一個(gè)不帶環(huán)，兩個(gè)鏈表一定不相交
????（3）連個(gè)鏈表都帶環(huán)，如果相交則可以分為以下三種情況
???? ?1）兩個(gè)鏈表在環(huán)外相交， 此時(shí)鏈表1 和鏈表2 對(duì)應(yīng)的環(huán)的入口地址是相等的
???? ?2）兩個(gè)鏈表在換上相交，此時(shí)從一個(gè)環(huán)的入口地址出發(fā)，一定可以到達(dá)另一個(gè)環(huán)的入口
???? ?3）如果不是以上兩種情況，則連個(gè)鏈表一定不相交

/***鏈表是否相交沒(méi)有環(huán) **/int LinkListHasCrossWithCircle(LinkNode* head1, LinkNode* head2) {if(head1 == NULL || head2 == NULL){return 0;}LinkNode* cur1 = head1;while(cur1 -> next != NULL){cur1 = cur1 -> next;}LinkNode* cur2 = head2;while(cur2 -> next != NULL){cur2 = cur2 -> next;}if(cur1 == cur2){return 1;}return 0; } /*** 鏈表是否相交，不確定有沒(méi)有環(huán) **/int LinkListHasCrossWithCircle2(LinkNode* head1, LinkNode* head2) {if(head1 == NULL || head2 == NULL){return 0;//兩鏈表至少一個(gè)為空} LinkNode* circle1 = LinkListHasCircle(head1);LinkNode* circle2 = LinkListHasCircle(head2);//兩個(gè)鏈表都不帶環(huán)if(circle1 == NULL && circle2 == NULL){return LinkListHasCrossWithCircle(head1, head2);}//兩鏈表都帶環(huán)else if(circle1 != NULL && circle2 != NULL){//在環(huán)外相交LinkNode* entry1 = LinkListGetCircleEntry(head1);LinkNode* entry2 = LinkListGetCircleEntry(head2);if(entry1 == entry2){return 1;}//再換上相交else if(entry1 != entry2){LinkNode* cur1 = entry1;//從一個(gè)環(huán)入口點(diǎn)出發(fā)可以到達(dá)另外一個(gè)環(huán)入口點(diǎn)，則證明相交while(cur1 != entry2){cur1 = cur1 -> next;}return 1;}//不是上述情況則沒(méi)有相交return 0;}//一個(gè)帶環(huán)一個(gè)不帶環(huán)，則一定不相交else if( ( circle1 == NULL && circle2 != NULL )|| (circle1 != NULL && circle2 == NULL)){return 0;} }

???????????????????????

2.求鏈表的交點(diǎn)

????求換的交點(diǎn)和上述判斷是否有環(huán)是一個(gè)思路，可以分為一下幾種情況
????（1）兩個(gè)鏈表都不帶環(huán)的情況下，先利用上面的函數(shù)判斷出連個(gè)鏈表是否相交，再求出兩個(gè)鏈表的長(zhǎng)度 size1， size2，再將兩個(gè)鏈表的長(zhǎng)度做差（長(zhǎng)的減短的）得到一個(gè)大于等于0 的數(shù) offset，再讓分別定義兩個(gè)指針 cur1, cur2, 指向 head1, head2, 然后讓長(zhǎng)鏈表對(duì)應(yīng)的 cur1(假定cur1所指的鏈表長(zhǎng)) 先走 offset 步，cur2 不動(dòng)，cur1 每走一步 offset 就減1， 等到 offset 等于 0 的時(shí)候這個(gè)時(shí)候就說(shuō)明兩個(gè)指針cur1, cur2 都相對(duì)于交點(diǎn)的距離相等， 這個(gè)時(shí)候讓 cur1, cur2 一起向后走，當(dāng)它們兩個(gè)指針?biāo)鶎?duì)應(yīng)的節(jié)點(diǎn)相同時(shí)， 此時(shí)這個(gè)相同的節(jié)點(diǎn)就是兩個(gè)鏈表的交點(diǎn)
????（2）當(dāng)兩個(gè)鏈表一個(gè)帶環(huán)，一個(gè)不帶環(huán)時(shí)， 此時(shí)鏈表一定不相交，直接返回空
????（3）當(dāng)兩個(gè)鏈表都有環(huán)時(shí)，分為一下三種情況
????? 1）兩個(gè)鏈表在環(huán)外相交，此時(shí)的交點(diǎn)求法如圖所示

?????
????? 2）連個(gè)鏈表在環(huán)上相交
?????????????????????????
????? 3）如果不是以上兩種，那么一定不相交

/** *環(huán)的相交點(diǎn)不帶環(huán)**/LinkNode* LinkListCrossPoint(LinkNode* head1, LinkNode* head2) {if(head1 == NULL || head2 == NULL){return NULL;//兩鏈表至少一個(gè)為空}int len1 = LinkListSize(head1);int len2 = LinkListSize(head2);LinkNode* cur1 = head1;LinkNode* cur2 = head2;int offset = 0;if(len1 > len2){offset = len1 - len2;for(; offset > 0; cur1 = cur1 -> next){offset--;}}else if(len2 > len1){offset = len2 - len1;for(; offset > 0; cur2 = cur2 -> next){offset--;}}for(; cur1 != cur2; cur1 = cur1 -> next, cur2 = cur2 -> next){;}return cur1; }/** *環(huán)的相交點(diǎn)帶環(huán)不帶環(huán)不確定**/LinkNode* LinkListCrossPoint2(LinkNode* head1, LinkNode* head2) {if(head1 == NULL || head2 == NULL) { return NULL;//兩鏈表至少一個(gè)為空,一定不相交} LinkNode* entry1 = LinkListGetCircleEntry(head1);LinkNode* entry2 = LinkListGetCircleEntry(head2);//如果兩個(gè)都不帶環(huán)，直接用第一個(gè)版本if(entry1 == NULL && entry2 == NULL){ return LinkListCrossPoint(head1, head2);} //如果一個(gè)帶環(huán)，一個(gè)不帶環(huán)，一定不相交if(( entry1 == NULL && entry2 != NULL ) || ( entry1 != NULL && entry2 == NULL )){ return NULL;} //如果兩個(gè)都有環(huán)LinkNode* cur1 = head1;LinkNode* cur2 = head2;if(entry1 != NULL && entry2 != NULL){ //環(huán)外相交if(entry1 == entry2){LinkNode* end = entry1;int size1 = 0;int size2 = 0;for(; cur1 != end; cur1 = cur1 -> next){size1++;}size1 = size1 + 1;for(; cur2 != end; cur2 = cur2 -> next){size2++;}size2 = size2 + 1;int offset = 0;if(size1 > size2){offset = size1 - size2; for(cur1 = head1, cur2 = head2; offset > 0; offset--){cur1 = cur1 -> next;}for(; cur1 != end && cur1 != cur2; cur1 = cur1 -> next, cur2 = cur2 -> next){;}return cur1;}else if(size2 > size1){offset = size2 - size1;for(cur1 = head1, cur2 = head2; offset > 0; offset--){cur2 = cur2 -> next;}for(; cur1 != end && cur1 != cur2; cur1 = cur1 -> next, cur2 = cur2 -> next){;}return cur1;}else//size1 = size2{for(cur1 = head1, cur2 = head2; cur1 != cur2 && cur1 != end && cur2 != end; cur1 = cur1 -> next, cur2 = cur2 -> next){ ;}return cur1;}}//環(huán)內(nèi)相交，相交點(diǎn)就是入口else if(entry1 != entry2){LinkNode* cur = entry1;for(; cur != entry2; cur = cur -> next){;}return entry2;cur = entry2;for(; cur != entry1; cur = cur -> next){;}return entry1;}//不是上述兩種情況，則不相交else{return NULL;} } }

????????????????

3.求連個(gè)鏈表的交集

????求交集就是分別定義兩個(gè)指針 cur1, cur2,指向兩個(gè)對(duì)應(yīng)的鏈表的首元素， 然后將 cur1 和 cur2 所指的鏈表的 data 進(jìn)行比較， 如果相等， 將這個(gè)結(jié)點(diǎn)插入到一個(gè)新鏈表中， 然后兩個(gè)指針 cur1, cur2, 一起向后走一步，如果不相等， 就將 data 值小的那個(gè)指針向后移動(dòng)， 而另外一個(gè)指針不動(dòng)， 在進(jìn)行比較，重復(fù)以上動(dòng)作，直到 cur1 或者 cur2 兩個(gè)中其中一個(gè)為空，則停止循環(huán)

LinkNode* LinkListUnionSet(LinkNode* head1, LinkNode* head2) {if(head1 == NULL || head2 == NULL){return NULL;//兩個(gè)鏈表至少有一個(gè)為空}LinkNode* cur1 = head1;LinkNode* cur2 = head2;LinkNode* new_head = NULL;LinkNode* new_tail = NULL;while(cur1 != NULL && cur2 != NULL){if(cur1 -> data < cur2 -> data){cur1 = cur1 -> next;}else if(cur1 -> data > cur2 -> data){cur2 = cur2 -> next;}else{if(new_head == NULL){new_head = LinkNodeCreat(cur1 -> data);new_tail = new_head;}else{new_tail -> next = LinkNodeCreat(cur1 -> data);new_tail = new_tail -> next;}cur1 = cur1 -> next; cur2 = cur2 -> next;}}return new_head; }

4. 拷貝復(fù)雜鏈表

????先看一下復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)

typedef struct ComplexNode {LinkNodeType data;struct ComplexNode* next;struct ComplexNode* random; }ComplexNode;

????復(fù)雜鏈表中除了 data, next, 之外，還有一個(gè) random， 它可能指向鏈表中的如何一個(gè)節(jié)點(diǎn)， 還可能指向空。
????在進(jìn)行復(fù)雜鏈表的拷貝時(shí)， 可以采用下面的方法， 先將復(fù)雜鏈表按照簡(jiǎn)單鏈表進(jìn)行復(fù)制，將其復(fù)制到一個(gè)新鏈表中， 此時(shí)的新鏈表還是一個(gè)簡(jiǎn)單鏈表， 然后再遍歷舊鏈表，求出每一個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的 random 相對(duì)于頭節(jié)點(diǎn)的偏移量， 再遍歷新鏈表， 根據(jù)所求得的偏移量確定新鏈表中的 random 的指針的指向。

/*** 復(fù)雜鏈表的拷貝**/ ComplexNode* ComplexCopy(ComplexNode* head) {if(head == NULL){return NULL;//空鏈表}ComplexNode* cur = head;ComplexNode* new_head = NULL;ComplexNode* new_tail = NULL;while(cur != NULL){if(new_head == NULL){new_head = head ;new_tail = new_head;}else{new_tail -> next = cur;new_tail = new_tail -> next;}cur = cur -> next;}//求每個(gè)random相對(duì)于頭結(jié)點(diǎn)的偏移量int offset = 0;ComplexNode* new_cur = new_head;for(cur = head; cur != NULL; cur = cur -> next,new_cur = new_cur -> next){//求出每個(gè)結(jié)點(diǎn)相對(duì)于head的偏移量offset = Diff(head, cur -> random);//修改新鏈表中的random的值new_cur -> random = Step(new_head, offset);}return new_head; }/* ** 通過(guò)offset找到random**/ComplexNode* Step(ComplexNode* head, int offset) {if(head == NULL){ return NULL;//空鏈表} if(offset == -1){ return NULL;} ComplexNode* cur = head;ComplexNode* random = head;//讓 random 走 offset 步，再將 cur -> random = randomfor(; offset > 0; offset --){ random = random -> next;} return random; }/*** 求出每個(gè)結(jié)點(diǎn)相對(duì)于head的偏移量**/int Diff(ComplexNode* head, ComplexNode* random) {if(head == NULL){return -2;}if(random == NULL){return -1;}ComplexNode* cur = head;ComplexNode* new_cur = random;int count = 0;while(cur != new_cur){count++;cur = cur -> next;}return count; }

總結(jié)

以上是生活随笔為你收集整理的链表相关笔试面试题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。