關于連結清單筆試題的一些收集

1.已知連結清單的頭結點head,寫一個函數把這個連結清單逆序

[cpp]  view plain copy

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

遞歸方法：

[cpp]  view plain copy

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.         reverse2(curnode->next);  
10.         curnode->next->next=curnode;  
11.         if(curnode == head)  
12.         {  
13.                 head=cur;  
14.                 cur = curnode;  
15.                 cur->next = NULL;  
16.         }  
17. }  

2.已知兩個連結清單head1 和head2 各自有序，請把它們合并成一個連結清單依然有序。

[cpp]  view plain copy

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

遞歸方法:

[cpp]  view plain copy

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.有一個連結清單L,其每個節點有2個指針，一個指針next指向連結清單的下個節點，另一個random随機指向連結清單中的任一個節點，可能是自己或者為空，寫一個程式，要求複制這個連結清單的結構并分析其複雜性

這個題目的方法很巧妙，将兩個連結清單連接配接起來形成一個連結清單，設定好random指針後再将兩個連結清單分割開來。

[cpp]  view plain copy

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. 找出單向連結清單中中間結點

兩個指針，一個步長為1，另一個步長為2.步長為2的走到底後步長為1的正好到中間。

[cpp]  view plain copy

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. 如何檢查一個單向連結清單上是否有環

同樣兩個指針，一個步長為1，另一個步長為2，如果兩個指針能相遇則有環。

[cpp]  view plain copy

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

6. 給定單連結清單(head)，如果有環的話請傳回從頭結點進入環的第一個節點。

設連結清單頭到環入口節點距離為x，環入口節點到兩個指針相遇節點距離為z，換長度為y，則有x+z+1=y,是以z=y-1-x，即一個指針從連結清單頭部開始移動，一個指針兩個指針相遇後一個節點開始移動，相遇的地方即為環入口

[cpp]  view plain copy

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.隻給定單連結清單中某個結點p(并非最後一個結點，即p->next!=NULL)指針，删除該結點。

将p後面那個節點的值複制到p，删除p後面的節點

[cpp]  view plain copy

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前面插入一個節點

在p後面插入新節點，将p的值與建立的節點值互換。

9.給定單連結清單頭結點，删除連結清單中倒數第k個結點

一個指針指向連結清單頭，另一個指針指向第k個指針，然後兩個指針一起移動，第二個指針到了末端則第一個指針就是倒數第k個節點

[cpp]  view plain copy

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. 判斷兩個連結清單是否相交。

兩種情況，如果連結清單有環，則先在環裡設定一個指針不動，另一個連結清單從頭開始移動，如果另一個連結清單能夠與環中的指針相遇則是相交。

如果沒有環，則判斷兩個連結清單的最後個節點是否相同，相同則相交

[cpp]  view plain copy

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. 兩個連結清單相交，找出交點

求出兩個連結清單的長度a和b，一個指針指向較短連結清單的頭head，另一個指針指向較長連結清單的第head+|a-b|，然後兩個指針一起移動，相遇處即為交點。

[cpp]  view plain copy

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