關于鏈表筆試題的一些收集

Kinetis 2013-12-24

展開全文

1.已知鏈表的頭結點head,寫一個函數(shù)把這個鏈表逆序

[cpp]view plaincopy
void List::reverse()  
{  
        list_node * p = head;  
        list_node * q = p->next;  
        list_node * r = NULL;  
        while(q){  
                r = q->next;  
                q->next = p;  
                p = q;  
                q = r;  
        }  
        head->next  = NULL;  
        head = p;  
}  

遞歸方法：

[cpp]view plaincopy
void List::reverse2(list_node * curnode)  
{  
        if(curnode ==NULL)curnode = head;  
        if(curnode->next==NULL)  
        {  
                cur = curnode;  
                return;  
        }  
  
        reverse2(curnode->next);  
        curnode->next->next=curnode;  
        if(curnode == head)  
        {  
                head=cur;  
                cur = curnode;  
                cur->next = NULL;  
        }  
}  

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

[cpp]view plaincopy
void List::merge(List & list)  
{         
        list_node * a = head;  
        list_node * b = list.head;  
        list_node * tempa= a;  
        list_node * tempb = b;  
        while(a&&b)   
        {  
                if(a->value <= b->value)  
                {  
                        while(a&&b&&a->value <= b->value)  
                        {  
                                tempa = a;  
                                a = a->next;  
                        }  
                        tempa->next=b;  
                }  
                else  
                {  
                        while(a&&b&&a->value > b->value)  
                        {  
                                tempb = b;  
                                b = b->next;  
                        }  
                        tempb->next=a;  
                }  
  
        }  
}  

遞歸方法:

[cpp]view plaincopy
list_node* List::recursive_merge(list_node * a,list_node * b)  
{  
        if(a == NULL)return b;  
        if(b == NULL)return a;  
        if(a->value <= b->value){  
                a->next=recursive_merge(a->next,b);  
                return a;  
        }  
        if(a->value > b->value)  
        {  
                b->next=recursive_merge(a,b->next);  
                return b;  
        }  
}  

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

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

[cpp]view plaincopy
List List::copyRndList()  
{  
        list_node * newhead = NULL;  
        list_node * newcur = NULL;  
        list_node * cur = head;  
        while(cur)  
        {  
                if(newhead == NULL){  
                        newhead = new list_node;  
                        newhead->value = cur->value;  
                        newhead->next = cur->next;  
                        cur->next = newhead;  
                }  
                else{  
                        newcur = new list_node;  
                        newcur->value = cur->value;  
                        newcur->next = cur->next;  
                        cur->next = newcur;  
                }  
                cur=cur->next->next;  
        }  
        cur = head;  
        while(cur){  
                if(cur->rnd)  
                        cur->next->rnd=cur->rnd->next;  
                else  
                        cur->next->rnd = NULL;  
                cur = cur->next->next;  
        }  
        cur = head;  
        list_node * dst = cur->next;  
        while(cur)  
        {  
                list_node * temp = dst->next;  
                cur->next = temp;  
                if(temp)dst->next = temp->next;  
                cur = cur->next;  
                dst=dst->next;  
        }  
        List newList;  
        newList.head = newhead;  
        return newList;  
}  

4. 找出單向鏈表中中間結點

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

[cpp]view plaincopy
list_node * List::middleElement()  
{  
        list_node * p = head;  
        list_node * q = head->next;  
        while(q){  
                p = p->next;  
                if(q)q=q->next;  
                if(q)q=q->next;  
        }  
}  

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

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

[cpp]view plaincopy
list_node * List::getJoinPointer()  
{  
  
        if(head == NULL || head->next == NULL)return NULL;  
        list_node * one = head;  
        list_node * two = head->next;  
        while(one != two){  
                one = one->next;  
                if(two)two=two->next;  
                else break;  
                if(two)two=two->next;  
                else break;  
        }  
        if(one == NULL || two == NULL)return NULL;  
        return one;  
}  

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

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

[cpp]view plaincopy
list_node * List::findCycleEntry()  
{  
        if(checkCycle()==false)return NULL;  
        list_node * joinPointer = getJoinPointer();  
        list_node * p = head;  
        list_node * q = joinPointer->next;  
        while(p!=q)  
        {  
                p=p->next;  
                q=q->next;  
        }  
        return p;  
}  

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

將p后面那個節(jié)點的值復制到p，刪除p后面的節(jié)點

[cpp]view plaincopy
void List::deleteByPointer(list_node * node)  
{  
        if(node)  
        {  
                if(node->next){  
                        node->value = node->next->value;  
                        node->next = node->next->next;  
                }  
        }  
}  

8.在p前面插入一個節(jié)點

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

9.給定單鏈表頭結點，刪除鏈表中倒數(shù)第k個結點

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

[cpp]view plaincopy
list_node * List::lastKelement(int k){  
        int t = k;  
        list_node * p = head;  
        while(p&&t){  
                p=p->next;  
                t--;  
        }  
        if(p == NULL && t >0)return NULL;  
        list_node * q=head;  
        while(q && p){  
                p=p->next;  
                q=q->next;  
        }  
        return q;  
}  

10. 判斷兩個鏈表是否相交。

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

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

[cpp]view plaincopy
bool List::isIntersecting(const List & list)  
{  
        bool flag = false;  
        if(this->checkCycle())  
        {  
                list_node * p = getJoinPointer();  
                list_node * q = list.head;  
                while(q){  
                        if(q == p){  
                                flag = true;  
                                break;  
                        }  
                        q=q->next;  
                }  
                flag = true;  
        }  
        else  
        {  
                list_node * p = head;  
                list_node * q = list.head;  
                while(p->next)p=p->next;  
                while(q->next)q=q->next;  
                if(p  == q)flag = true;  
                else flag =false;  
        }  
        return flag;  
}  

11. 兩個鏈表相交，找出交點

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

[cpp]view plaincopy
list_node * List::intersectNode(const List & list)  
{  
        if(!isIntersecting(list))return NULL;  
        int a = cnt;  
        int b = list.cnt;  
        list_node * p;  
        list_node * q;  
        if(a<b){p=list.head;q = head;}  
        else {p = head; q=list.head;}  
        a = abs(cnt - list.cnt);  
        while(p && a)  
        {  
                p = p->next;  
                a--;  
        }  
        while(p&&q)  
        {  
                if(q==p)break;  
                p=p->next;  
                q=q->next;  
        }  
        if(p && q && p == q)return p;  
        return NULL;  
}  