鏈表相關筆試面試題

1.判斷兩個鏈表是否相交

????兩個鏈表是否相交可分為以下幾種情況
????（1）兩個鏈表都不帶環，此時兩個鏈表所對應的最后一個節點是相等的
????（2）兩個鏈表一個帶環，一個不帶環，兩個鏈表一定不相交
????（3）連個鏈表都帶環，如果相交則可以分為以下三種情況
???? ?1）兩個鏈表在環外相交，此時鏈表1 和鏈表2 對應的環的入口地址是相等的
???? ?2）兩個鏈表在換上相交，此時從一個環的入口地址出發，一定可以到達另一個環的入口
???? ?3）如果不是以上兩種情況，則連個鏈表一定不相交

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

??????????????????????? 這里寫圖片描述

2.求鏈表的交點

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

????? 這里寫圖片描述
????? 2）連個鏈表在環上相交
?????????????????????????
????? 3）如果不是以上兩種，那么一定不相交

/**                                                                                                                                                             *環的相交點不帶環**/LinkNode* LinkListCrossPoint(LinkNode* head1, LinkNode* head2)
{if(head1 == NULL || head2 == NULL){return NULL;//兩鏈表至少一個為空}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;                                                                                                                                               
}/**                                                                                                                                                             *環的相交點帶環不帶環不確定**/LinkNode* LinkListCrossPoint2(LinkNode* head1, LinkNode* head2)
{if(head1 == NULL || head2 == NULL)                                                                                                                       {    return NULL;//兩鏈表至少一個為空,一定不相交}    LinkNode* entry1 = LinkListGetCircleEntry(head1);LinkNode* entry2 = LinkListGetCircleEntry(head2);//如果兩個都不帶環，直接用第一個版本if(entry1 == NULL && entry2 == NULL){    return LinkListCrossPoint(head1, head2);}    //如果一個帶環，一個不帶環，一定不相交if(( entry1 == NULL && entry2 != NULL ) || ( entry1 != NULL && entry2 == NULL )){    return NULL;}    //如果兩個都有環LinkNode* cur1 = head1;LinkNode* cur2 = head2;if(entry1 != NULL && entry2 != NULL){    
//環外相交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;}}//環內相交，相交點就是入口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.求連個鏈表的交集

????求交集就是分別定義兩個指針 cur1, cur2,指向兩個對應的鏈表的首元素，然后將 cur1 和 cur2 所指的鏈表的 data 進行比較，如果相等，將這個結點插入到一個新鏈表中，然后兩個指針 cur1, cur2, 一起向后走一步，如果不相等，就將 data 值小的那個指針向后移動，而另外一個指針不動，在進行比較，重復以上動作，直到 cur1 或者 cur2 兩個中其中一個為空，則停止循環

LinkNode* LinkListUnionSet(LinkNode* head1, LinkNode* head2)
{if(head1 == NULL || head2 == NULL){return NULL;//兩個鏈表至少有一個為空}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. 拷貝復雜鏈表

????先看一下復雜鏈表的數據結構

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

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

/*** 復雜鏈表的拷貝**/                                                                                                                                                            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;}//求每個random相對于頭結點的偏移量int offset = 0;ComplexNode* new_cur = new_head;for(cur = head; cur != NULL; cur = cur -> next,new_cur = new_cur -> next){//求出每個結點相對于head的偏移量offset = Diff(head, cur -> random);//修改新鏈表中的random的值new_cur -> random = Step(new_head, offset);}return new_head;
}/*                                                                                                                                                             ** 通過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; 
}/*** 求出每個結點相對于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;
}