• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 297,  comments - 15,  trackbacks - 0

            題目:給你一個單向鏈表的頭指針,可能最后不是NULL終止,而是循環鏈表。題目問你怎么找出這個鏈表循環部分的第一個節點。比如下面的鏈表:
            0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循環
            當然盡量用少的空間和時間是題目的要求。
            (1).判斷指針A和B在環內首次相遇:
            有兩個指針A和B,從鏈表的頭節點出發,A的步長是1,B的步長是2,那么當他們在環內相遇時,設a是鏈表頭到環節點的位置,b是環的周長,c是A和B在環上首次相遇時與環節點的距離,m和n分別是第一次相遇時A和B走過的環數,那么:A經歷的路程是a+(m*b+c),B經歷的路程是a+(n*b+c),這時2*A經歷的路程=B經歷的路程,所以得到2*(a+m*b+c)=a+(n*b+c),即a+2mb+c=nb,即
                  a+c=(n-2m)b=k*b,k=n-2m -----(1)式.
            (2).判斷A和B在環節點相遇:
            指針A和B相遇后,如果需要二者相遇在循環鏈表的環節點,則指針A以步長1前進,需要路程b-c+x*b=(x+1)b-c,由1可知,a=kb-c,那么也就是說:指針A要到達環節點還需要走的路程kb-c正好等于a。這樣問題就解決了:A從首次相遇的位置步長為1走到環節點需要kb-c,那么B只需從頭節點步長為一走a個節點,就到達了環節點。這時A和B相遇。
            大功告成也!!!!!!!!!!!時間復雜度O(n),空間復雜度O(1)!!!!!!!!!!!!!!!!!!!!!!!!!
            posted on 2008-09-14 23:29 chatler 閱讀(1902) 評論(1)  編輯 收藏 引用 所屬分類: Algorithm

            FeedBack:
            # re: 一個關于單向鏈表的面試題
            2008-09-14 23:42 | chatler
            還有一種算法,就是用有向圖來實現(具體見下面代碼):
            把鏈表看成一個有向圖,深度優先遍歷該有向圖,判斷有無循環出現。

            懶得再用中文寫一遍具體算法了,看下面的代碼實現吧,英文注釋解釋的很清楚了。



            時間復雜度 O(e), 鏈表邊的總數。

            空間復雜度 O(1).

            有向圖采用鄰接表實現。


            /* file: DFSDetectLoop.cpp */

            /*

            * Detect if the graph has loop -- For both Undigraph and digraph

            * Complexity: O(e); e is the number of arcs in Graph.

            *

            * BUG Reported:

            * 1. Apr-26-07

            * Not support Undigraph yet ! Fix me !!!

            * - Fixed on Apr-26-08.

            *

            * Return

            * 1 - Loop detected.

            * 0 - No loop detected.

            * *

            * Algrithm:

            * 1. Init all the nodes color to WHITE.

            * 2. DFS graph

            * For each the nodes v in graph, do step (1) and (2).

            * (1) If v is WHITE, DFS from node v:

            * (a) Mark v as GRAY.

            * (b) For every nodes tv adjacent with node v,

            * (i) If the current visiting node is gray, then loop detected. exit.

            * (ii) Goto Step (1).

            * (iii) All the nodes on sub-tree of tv have been visited. Mark node tv as BLACK.

            * (2) All the nodes on sub-tree of v have been visited. Mark node v as BLACK.

            *

            * Function DFSDetectLoop is valid for both Undigraph and digraph.

            *

            * */

            int DFSDetectLoop (ALGraph *graph, int VisitFunc (ALGraph *graph, int v))

            {

            int v;



            for (v = 0; v < graph->vexnum; v++)

            {

            MarkNodeColor (graph, v, WHITE);

            }

            for (v = 0; v < graph->vexnum; v++)

            {

            if (graph->vertices[v].color == WHITE)

            {

            /* We are good to call DFSDetectLoopSub the first

            * time with pv = -1, because no node equals -1.

            * */

            if (1 == DFSDetectLoopSub (graph, v, -1, VisitFunc))

            return 1;

            }

            MarkNodeColor (graph, v, BLACK);

            }

            return 1;

            }



            /*

            * Start from node v, DFS graph to detect loop.

            * pv is the node that just visited v. pv is used to avoid v to visit pv again.

            * pv is introduced to support Undigraph.

            *

            * NOTE:

            * Before calling DFSDetectLoopSub, make sure node v is not visited yet.

            * */

            int DFSDetectLoopSub (ALGraph *graph, int v, int pv, int VisitFunc (ALGraph *graph, int v))

            {

            assert (graph->vertices[v].color == WHITE);



            MarkNodeColor (graph, v, GRAY);



            VisitFunc (graph, v);



            ArcNode *arc;

            arc = graph->vertices[v].firstarc;

            while (arc)

            {

            int tv = arc->adjvex;



            /* For Undigraph, if tv equals pv, this arc should not be count.

            * Because we have just visited from pv to v.

            * Just go ahead to check next vertex connected with v.

            * 1----2, after visit 1, we will visit 2, while visiting 2, 1 will be the 1st node visited.

            *

            * For digraph, we need to check loop even tv equals pv.

            * Because there is case that node v points to u, and u points to v.

            * */

            if ((graph->kind == AG) && (tv != pv))

            {

            if ( graph->vertices[tv].color == GRAY )

            {

            cout << "Gray node visited at node: " << tv + 1 <<endl;

            cout << "DFSDetectLoopSub: Loop Detected at from node " << v + 1<<" to "<< tv + 1 <<" !" <<endl;

            return 1;

            }



            if (graph->vertices[tv].color == WHITE)

            {

            if (1 == DFSDetectLoopSub (graph, tv, v, VisitFunc))

            {

            return 1;

            }

            }

            /* At this line:

            * (1)If tv's color is already BLACK; Go ahead checking next arc;

            * (2)If the sub-tree of node tv has all been visited, mark as BLACK and check next arc;

            * Backward tv to to v's other adjacent node. So tv should be marked as black.

            * */

            MarkNodeColor (graph, tv, BLACK);

            }



            arc = arc->nextarc;

            }

            return 0;

            }
              回復  更多評論
              
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(10)

            隨筆分類(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

            • cloudward
            • 感覺這個博客還是不錯,雖然做的東西和我不大相關,覺得看看還是有好處的

            network

            OSS

            • Google Android
            • Android is a software stack for mobile devices that includes an operating system, middleware and key applications. This early look at the Android SDK provides the tools and APIs necessary to begin developing applications on the Android platform using the Java programming language.
            • os161 file list

            overall

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久中文字幕视频、最近更新| 亚洲∧v久久久无码精品| 久久婷婷五月综合国产尤物app| 99久久99久久精品国产片果冻| 一本一道久久综合狠狠老| 97精品久久天干天天天按摩| 人妻系列无码专区久久五月天| 久久婷婷色综合一区二区| 久久精品中文无码资源站| 久久无码精品一区二区三区| 久久狠狠爱亚洲综合影院| 超级碰久久免费公开视频| 亚洲av伊人久久综合密臀性色 | 麻豆精品久久精品色综合| 色婷婷噜噜久久国产精品12p| 色综合久久无码五十路人妻| 久久久久亚洲AV成人网人人网站| 久久国产欧美日韩精品| 欧美精品九九99久久在观看| 久久国产精品成人免费| 狼狼综合久久久久综合网| 一级女性全黄久久生活片免费| 国产午夜久久影院| 久久丫精品国产亚洲av| 亚洲七七久久精品中文国产| 韩国三级中文字幕hd久久精品| 久久久久人妻精品一区二区三区 | 精品久久久久久无码中文字幕| 国产成人久久精品一区二区三区| 伊人久久精品影院| 午夜精品久久久内射近拍高清| 国产成人香蕉久久久久| 久久96国产精品久久久| 国内精品久久人妻互换| 精品人妻久久久久久888| 亚洲精品国产字幕久久不卡| 中文字幕日本人妻久久久免费 | 久久线看观看精品香蕉国产| 好属妞这里只有精品久久| 久久国产精品-久久精品| 女人香蕉久久**毛片精品|