小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

關(guān)于鏈表筆試題的一些收集

 Kinetis 2013-12-24

1.已知鏈表的頭結(jié)點(diǎn)head,寫一個(gè)函數(shù)把這個(gè)鏈表逆序

  1. void List::reverse()  
  2. {  
  3.         list_node * p = head;  
  4.         list_node * q = p->next;  
  5.         list_node * r = NULL;  
  6.         while(q){  
  7.                 r = q->next;  
  8.                 q->next = p;  
  9.                 p = q;  
  10.                 q = r;  
  11.         }  
  12.         head->next  = NULL;  
  13.         head = p;  
  14. }  

遞歸方法：

  1. void List::reverse2(list_node * curnode)  
  2. {  
  3.         if(curnode ==NULL)curnode = head;  
  4.         if(curnode->next==NULL)  
  5.         {  
  6.                 cur = curnode;  
  7.                 return;  
  8.         }  
  9.   
  10.         reverse2(curnode->next);  
  11.         curnode->next->next=curnode;  
  12.         if(curnode == head)  
  13.         {  
  14.                 head=cur;  
  15.                 cur = curnode;  
  16.                 cur->next = NULL;  
  17.         }  
  18. }  

2.已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。

  1. void List::merge(List & list)  
  2. {         
  3.         list_node * a = head;  
  4.         list_node * b = list.head;  
  5.         list_node * tempa= a;  
  6.         list_node * tempb = b;  
  7.         while(a&&b)   
  8.         {  
  9.                 if(a->value <= b->value)  
  10.                 {  
  11.                         while(a&&b&&a->value <= b->value)  
  12.                         {  
  13.                                 tempa = a;  
  14.                                 a = a->next;  
  15.                         }  
  16.                         tempa->next=b;  
  17.                 }  
  18.                 else  
  19.                 {  
  20.                         while(a&&b&&a->value > b->value)  
  21.                         {  
  22.                                 tempb = b;  
  23.                                 b = b->next;  
  24.                         }  
  25.                         tempb->next=a;  
  26.                 }  
  27.   
  28.         }  
  29. }  

遞歸方法:

  1. list_node* List::recursive_merge(list_node * a,list_node * b)  
  2. {  
  3.         if(a == NULL)return b;  
  4.         if(b == NULL)return a;  
  5.         if(a->value <= b->value){  
  6.                 a->next=recursive_merge(a->next,b);  
  7.                 return a;  
  8.         }  
  9.         if(a->value > b->value)  
  10.         {  
  11.                 b->next=recursive_merge(a,b->next);  
  12.                 return b;  
  13.         }  
  14. }  

3.有一個(gè)鏈表L,其每個(gè)節(jié)點(diǎn)有2個(gè)指針，一個(gè)指針next指向鏈表的下個(gè)節(jié)點(diǎn)，另一個(gè)random隨機(jī)指向鏈表中的任一個(gè)節(jié)點(diǎn)，可能是自己或者為空，寫一個(gè)程序，要求復(fù)制這個(gè)鏈表的結(jié)構(gòu)并分析其復(fù)雜性

這個(gè)題目的方法很巧妙，將兩個(gè)鏈表連接起來形成一個(gè)鏈表，設(shè)置好random指針后再將兩個(gè)鏈表分割開來。

 

  1. List List::copyRndList()  
  2. {  
  3.         list_node * newhead = NULL;  
  4.         list_node * newcur = NULL;  
  5.         list_node * cur = head;  
  6.         while(cur)  
  7.         {  
  8.                 if(newhead == NULL){  
  9.                         newhead = new list_node;  
  10.                         newhead->value = cur->value;  
  11.                         newhead->next = cur->next;  
  12.                         cur->next = newhead;  
  13.                 }  
  14.                 else{  
  15.                         newcur = new list_node;  
  16.                         newcur->value = cur->value;  
  17.                         newcur->next = cur->next;  
  18.                         cur->next = newcur;  
  19.                 }  
  20.                 cur=cur->next->next;  
  21.         }  
  22.         cur = head;  
  23.         while(cur){  
  24.                 if(cur->rnd)  
  25.                         cur->next->rnd=cur->rnd->next;  
  26.                 else  
  27.                         cur->next->rnd = NULL;  
  28.                 cur = cur->next->next;  
  29.         }  
  30.         cur = head;  
  31.         list_node * dst = cur->next;  
  32.         while(cur)  
  33.         {  
  34.                 list_node * temp = dst->next;  
  35.                 cur->next = temp;  
  36.                 if(temp)dst->next = temp->next;  
  37.                 cur = cur->next;  
  38.                 dst=dst->next;  
  39.         }  
  40.         List newList;  
  41.         newList.head = newhead;  
  42.         return newList;  
  43. }  

4. 找出單向鏈表中中間結(jié)點(diǎn)

兩個(gè)指針，一個(gè)步長(zhǎng)為1，另一個(gè)步長(zhǎng)為2.步長(zhǎng)為2的走到底后步長(zhǎng)為1的正好到中間。

  1. list_node * List::middleElement()  
  2. {  
  3.         list_node * p = head;  
  4.         list_node * q = head->next;  
  5.         while(q){  
  6.                 p = p->next;  
  7.                 if(q)q=q->next;  
  8.                 if(q)q=q->next;  
  9.         }  
  10. }  

5. 如何檢查一個(gè)單向鏈表上是否有環(huán)

同樣兩個(gè)指針，一個(gè)步長(zhǎng)為1，另一個(gè)步長(zhǎng)為2，如果兩個(gè)指針能相遇則有環(huán)。

  1. list_node * List::getJoinPointer()  
  2. {  
  3.   
  4.         if(head == NULL || head->next == NULL)return NULL;  
  5.         list_node * one = head;  
  6.         list_node * two = head->next;  
  7.         while(one != two){  
  8.                 one = one->next;  
  9.                 if(two)two=two->next;  
  10.                 else break;  
  11.                 if(two)two=two->next;  
  12.                 else break;  
  13.         }  
  14.         if(one == NULL || two == NULL)return NULL;  
  15.         return one;  
  16. }  

6. 給定單鏈表(head)，如果有環(huán)的話請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。

設(shè)鏈表頭到環(huán)入口節(jié)點(diǎn)距離為x，環(huán)入口節(jié)點(diǎn)到兩個(gè)指針相遇節(jié)點(diǎn)距離為z，換長(zhǎng)度為y，則有x+z+1=y,所以z=y-1-x，即一個(gè)指針從鏈表頭部開始移動(dòng)，一個(gè)指針兩個(gè)指針相遇后一個(gè)節(jié)點(diǎn)開始移動(dòng)，相遇的地方即為環(huán)入口

  1. list_node * List::findCycleEntry()  
  2. {  
  3.         if(checkCycle()==false)return NULL;  
  4.         list_node * joinPointer = getJoinPointer();  
  5.         list_node * p = head;  
  6.         list_node * q = joinPointer->next;  
  7.         while(p!=q)  
  8.         {  
  9.                 p=p->next;  
  10.                 q=q->next;  
  11.         }  
  12.         return p;  
  13. }  

7.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)。

將p后面那個(gè)節(jié)點(diǎn)的值復(fù)制到p，刪除p后面的節(jié)點(diǎn)

  1. void List::deleteByPointer(list_node * node)  
  2. {  
  3.         if(node)  
  4.         {  
  5.                 if(node->next){  
  6.                         node->value = node->next->value;  
  7.                         node->next = node->next->next;  
  8.                 }  
  9.         }  
  10. }  

8.在p前面插入一個(gè)節(jié)點(diǎn)

在p后面插入新節(jié)點(diǎn)，將p的值與新建的節(jié)點(diǎn)值互換。

 

9.給定單鏈表頭結(jié)點(diǎn)，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

一個(gè)指針指向鏈表頭，另一個(gè)指針指向第k個(gè)指針，然后兩個(gè)指針一起移動(dòng)，第二個(gè)指針到了末端則第一個(gè)指針就是倒數(shù)第k個(gè)節(jié)點(diǎn)

  1. list_node * List::lastKelement(int k){  
  2.         int t = k;  
  3.         list_node * p = head;  
  4.         while(p&&t){  
  5.                 p=p->next;  
  6.                 t--;  
  7.         }  
  8.         if(p == NULL && t >0)return NULL;  
  9.         list_node * q=head;  
  10.         while(q && p){  
  11.                 p=p->next;  
  12.                 q=q->next;  
  13.         }  
  14.         return q;  
  15. }  

 

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

兩種情況，如果鏈表有環(huán)，則先在環(huán)里設(shè)定一個(gè)指針不動(dòng)，另一個(gè)鏈表從頭開始移動(dòng)，如果另一個(gè)鏈表能夠與環(huán)中的指針相遇則是相交。

如果沒有環(huán)，則判斷兩個(gè)鏈表的最后個(gè)節(jié)點(diǎn)是否相同，相同則相交

  1. bool List::isIntersecting(const List & list)  
  2. {  
  3.         bool flag = false;  
  4.         if(this->checkCycle())  
  5.         {  
  6.                 list_node * p = getJoinPointer();  
  7.                 list_node * q = list.head;  
  8.                 while(q){  
  9.                         if(q == p){  
  10.                                 flag = true;  
  11.                                 break;  
  12.                         }  
  13.                         q=q->next;  
  14.                 }  
  15.                 flag = true;  
  16.         }  
  17.         else  
  18.         {  
  19.                 list_node * p = head;  
  20.                 list_node * q = list.head;  
  21.                 while(p->next)p=p->next;  
  22.                 while(q->next)q=q->next;  
  23.                 if(p  == q)flag = true;  
  24.                 else flag =false;  
  25.         }  
  26.         return flag;  
  27. }  

 

11. 兩個(gè)鏈表相交，找出交點(diǎn)

求出兩個(gè)鏈表的長(zhǎng)度a和b，一個(gè)指針指向較短鏈表的頭head，另一個(gè)指針指向較長(zhǎng)鏈表的第head+|a-b|，然后兩個(gè)指針一起移動(dòng)，相遇處即為交點(diǎn)。

  1. list_node * List::intersectNode(const List & list)  
  2. {  
  3.         if(!isIntersecting(list))return NULL;  
  4.         int a = cnt;  
  5.         int b = list.cnt;  
  6.         list_node * p;  
  7.         list_node * q;  
  8.         if(a<b){p=list.head;q = head;}  
  9.         else {p = head; q=list.head;}  
  10.         a = abs(cnt - list.cnt);  
  11.         while(p && a)  
  12.         {  
  13.                 p = p->next;  
  14.                 a--;  
  15.         }  
  16.         while(p&&q)  
  17.         {  
  18.                 if(q==p)break;  
  19.                 p=p->next;  
  20.                 q=q->next;  
  21.         }  
  22.         if(p && q && p == q)return p;  
  23.         return NULL;  
  24. }  

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多