常用于面試的鏈表操作算法

比較有趣的鏈表操作
服務器君一共花費了162.271 ms進行了5次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

鏈表操作在面試中會經常出現,下面列舉的鏈表操作方法是比較典型的。

問題1:輸入一個單向鏈表,輸出該鏈表中倒數第k個結點

一個單向鏈表無法像數組一樣可以直接索引,那么要找到鏈表的倒數第K個節點該怎么操作呢,其實思路非常簡單,我們只需要設置兩個指針p1,p2,首先p1和p2都指向鏈表的頭部head,然后p2向前走k步,這樣p1和p2之間就間隔k個節點,最后p1和p2同時向前移動,直至p2走到鏈表末尾,然后返回p1就是我們要找的鏈表的倒數K個節點。

struct ListNode{
    char data;
    ListNode *next;
};
ListNode *head, *p1, *p2;
ListNode *func(ListNode *head, int k){
    assert(k>=0);   //保證k應該要大于0
    p1 = p2 = head;
    for (; k>0; k--)
        p2 = p2->next;  //移動p2到與p1距離k個位置
    if (k>0)
        return   //要考慮到鏈表的元素可以小于k個
    while(p2!=NULL){
        p2 = p2->next;
        p1 = p1->next;     //移動p1,p2直到p2到達最后
}
return p1;
}

問題2:如何判斷一個鏈表有環

這個問題可以這么來分析我們可以設置兩個指針(p1, p2),初始值都指向頭,p1每次前進一步,p2每次前進二步,如果鏈表存在環,則p2先進入環,p1后進入環,兩個指針在環中走動,必定相遇,如何兩節點相遇說明了這個鏈表存在一個環,以此思路給出了一下代碼片段:

struct Node{
    int data;
    Node *next;
}
bool isCircle(Node *head, Node *CircleNode, Node *lastNode){
    Node *fast = head->next;  //步長為2的節點
    Node *slow = head;   //步長為1的節點
    while(fast != slow && fast && slow){  //當兩節點不相遇且還未到達末尾時進行循環
        if (fast->next != NULL)
            fast = fast->next;
        if (fast->next ==NULL)
            lastNode = fast;    //記錄尾節點
        if (slow->next = NULL)
            lastNode = slow;  //記錄尾節點
        fast = fast->next;
        slow= slow->next;
}
if (fast == slow && fast && slow){
    CircleNode = fast;   //記錄相遇的節點
    return True;
}
else
    return false;
}

問題3:如何判斷兩個鏈表是否相交

分析:問題可以分為兩種情況,第一種情況如果兩個鏈表都沒有環的話,那么兩個鏈表要是相交,那么從他們相交的那一點開始到尾節點兩個鏈表應該完全相同,這樣我們就可以直接判斷鏈表的尾節點是否相同來進行判斷兩鏈表是否相交來進行判斷。第二種情況的話如果兩個鏈表存在環的話,那么我們則應該判斷一鏈表上倆指針相遇的那個節點,在不在另一條鏈表上,如果在,則相交,如果不在,則不相交。由此可給出下面的代碼片段:

bool detect(Node *head1, Node *head2){
    Node *circleNode1;   //鏈表1的相交節點
    Node *circleNode2;   //鏈表2的相交節點
    Node *lastNode1;     //鏈表1的尾節點
    Node *lastNode2;     //鏈表2的尾節點
    bool isCircle1 = isCircle(head1, circleNode1, lastNode1);   //判斷鏈表1是否存在環
    bool isCircle2 = isCircle(head2, circleNode2, lastNode2);  //判斷鏈表2是否存在環
    if (isCircle1 != isCircle2)
        return false;
    else if (!isCircle1 && !isCircle2){  //如果兩鏈表都不存在環可以直接對尾節點進行比較看是否相交
        return lastNode1 == lastNode2;
}
else{              //如果連鏈表都存在環的話要看相交節點是不是在兩鏈表都出現
    Node *temp = circleNode1->next;
    while(temp != circleNode1){
        if (temp == circleNode2)
            return true;
        temp = temp->next;
}
return false;
}
return false;
}

大概就這樣,希望對你面試有用。

本文地址:http://www.824886.live/librarys/veda/detail/780,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.824886.live/librarys/veda/detail/780

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏。

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《PHP經典實例(第2版)》 斯克拉(David Sklar) (作者), 切貝特伯格(Adam Tracbtenberg) (作者), 李松峰 (譯者), 秦緒文 (譯者), 李麗 (譯者)

PHP經典實例(第2版)能夠為您節省寶貴的Web開發時間。有了這些針對真實問題的解決方案放在手邊,大多數編程難題都會迎刃而解?!禤HP經典實例(第2版)》將PHP的特性與經典實例叢書的獨特形式組合到一起,足以幫您成功地構建跨瀏覽器的Web應用程序。在這個修訂版中,您可以更加方便地找到各種編程問題的解決方案,《PHP經典實例(第2版)》中內容涵蓋了:表單處理;Session管理;數據庫交互;使用Web服務。

更多計算機寶庫...

云南快乐十分走势一定牛 pk10免费计划软件手机 体彩排列5开奖结果 陕西快乐10分投注 有15万存款怎么理财 青海11选5购买软件 云南十一选五遗漏值 上海时时乐开奖公告 内蒙古十一远五一定牛 体育彩票排列三走势图 河南体育彩票十一选五