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

            }
              回復  更多評論
              
            <2009年11月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            思思久久好好热精品国产| 亚洲国产精品一区二区久久| 久久午夜综合久久| 国产69精品久久久久777| 久久亚洲中文字幕精品有坂深雪| 久久综合给久久狠狠97色 | 久久精品国产一区| 久久高潮一级毛片免费| 亚洲国产精品一区二区久久hs| 97久久久久人妻精品专区 | 久久精品视频91| 久久亚洲AV成人出白浆无码国产| 久久精品国产久精国产| 久久亚洲国产最新网站| 国产精品久久久久久久| 综合网日日天干夜夜久久 | 国产亚洲精久久久久久无码| 久久人人超碰精品CAOPOREN | 国产精品午夜久久| 久久成人国产精品| 一本色道久久88—综合亚洲精品| 国产福利电影一区二区三区,免费久久久久久久精 | 精品久久久久久久中文字幕| 人妻精品久久无码专区精东影业 | 久久se精品一区精品二区| 久久精品国产精品亚洲精品 | 久久亚洲AV无码精品色午夜麻豆| 久久久中文字幕| 久久成人国产精品| 日韩精品久久久久久免费| 伊人久久国产免费观看视频| 久久精品国产99国产精品| 亚洲国产精品久久久久久| 久久精品国产91久久综合麻豆自制| 人妻精品久久无码区| 久久精品www人人爽人人| 久久精品亚洲一区二区三区浴池| 国产成人精品久久| 人妻无码中文久久久久专区| 久久精品一本到99热免费| 久久亚洲AV成人无码电影|