• <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 閱讀(1906) 評論(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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            日韩精品久久久久久久电影蜜臀 | 伊人久久大香线蕉成人| 久久露脸国产精品| 2021国产精品午夜久久| 久久久久女人精品毛片| 久久www免费人成看国产片| 久久热这里只有精品在线观看| 久久亚洲欧美国产精品| 久久人人爽人人爽人人片AV麻豆 | 久久伊人五月天论坛| 久久久久人妻一区精品色| 久久国产影院| 精品久久一区二区三区| 久久久久久免费视频| 精品久久久久久无码中文野结衣 | 久久精品欧美日韩精品| 香港aa三级久久三级老师2021国产三级精品三级在 | 日本福利片国产午夜久久| 久久久久亚洲AV无码专区首JN| 天天久久狠狠色综合| 亚洲AV无码成人网站久久精品大| 久久久青草青青国产亚洲免观| 国产精品视频久久| 久久久久亚洲AV无码专区体验| 怡红院日本一道日本久久 | 伊色综合久久之综合久久| 久久99国产精品99久久| 久久综合九色综合网站| 无码人妻少妇久久中文字幕 | 99久久国产综合精品麻豆| 91麻豆国产精品91久久久| 久久久WWW免费人成精品| 国内精品久久久久久久涩爱| 久久久91精品国产一区二区三区 | 国产精品内射久久久久欢欢| 久久久老熟女一区二区三区| 久久夜色精品国产欧美乱| 性欧美丰满熟妇XXXX性久久久 | 婷婷久久综合九色综合绿巨人| 久久久久亚洲AV成人网人人软件| 国产午夜福利精品久久|