• <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

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

            FeedBack:
            # re: 一個(gè)關(guān)于單向鏈表的面試題
            2008-09-14 23:42 | chatler
            還有一種算法,就是用有向圖來(lái)實(shí)現(xiàn)(具體見(jiàn)下面代碼):
            把鏈表看成一個(gè)有向圖,深度優(yōu)先遍歷該有向圖,判斷有無(wú)循環(huán)出現(xiàn)。

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



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

            空間復(fù)雜度 O(1).

            有向圖采用鄰接表實(shí)現(xiàn)。


            /* 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;

            }
              回復(fù)  更多評(píng)論
              
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(10)

            隨筆分類(lèi)(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

            • cloudward
            • 感覺(jué)這個(gè)博客還是不錯(cuò),雖然做的東西和我不大相關(guān),覺(jué)得看看還是有好處的

            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

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久无码人妻精品一区二区三区 | 久久精品成人欧美大片| 国产精品对白刺激久久久| 久久精品国产精品亚洲精品| 日本福利片国产午夜久久| 欧美国产成人久久精品| 热re99久久精品国99热| 国产一区二区三精品久久久无广告 | 久久婷婷五月综合97色直播 | 国产精品99久久精品爆乳| 亚洲精品tv久久久久久久久久| 久久精品国产亚洲av麻豆图片| 国产精品久久精品| 久久久久久久91精品免费观看| 精品久久久久久久久中文字幕| 7777精品伊人久久久大香线蕉| 久久青青草原综合伊人| 无码人妻久久一区二区三区免费 | 国产精品一久久香蕉国产线看| 国产成人精品久久一区二区三区av | 久久精品一本到99热免费| 久久夜色tv网站| 久久不见久久见免费视频7| 久久亚洲高清综合| 久久成人精品| 国产精品成人精品久久久| 精品久久久久久无码专区| 97精品依人久久久大香线蕉97 | 91精品国产91久久| 久久99国产精品久久99果冻传媒 | 亚洲欧美成人综合久久久| 中文字幕精品无码久久久久久3D日动漫 | 精品国产青草久久久久福利| 办公室久久精品| 99久久精品费精品国产| 99久久国产主播综合精品 | 久久婷婷五月综合成人D啪| 亚洲婷婷国产精品电影人久久| 香港aa三级久久三级老师2021国产三级精品三级在 | 91精品国产91久久久久久| 97精品伊人久久久大香线蕉 |