青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 297,  comments - 15,  trackbacks - 0

題目:給你一個(gè)單向鏈表的頭指針,可能最后不是NULL終止,而是循環(huá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的步長是1,B的步長是2,那么當(dāng)他們?cè)诃h(huán)內(nèi)相遇時(shí),設(shè)a是鏈表頭到環(huán)節(jié)點(diǎn)的位置,b是環(huán)的周長,c是A和B在環(huán)上首次相遇時(shí)與環(huán)節(jié)點(diǎn)的距離,m和n分別是第一次相遇時(shí)A和B走過的環(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以步長1前進(jìn),需要路程b-c+x*b=(x+1)b-c,由1可知,a=kb-c,那么也就是說:指針A要到達(dá)環(huán)節(jié)點(diǎn)還需要走的路程kb-c正好等于a。這樣問題就解決了:A從首次相遇的位置步長為1走到環(huán)節(jié)點(diǎn)需要kb-c,那么B只需從頭節(jié)點(diǎn)步長為一走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 閱讀(1911) 評(píng)論(1)  編輯 收藏 引用 所屬分類: Algorithm

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

懶得再用中文寫一遍具體算法了,看下面的代碼實(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)論
  
<2008年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用鏈接

留言簿(10)

隨筆分類(307)

隨筆檔案(297)

algorithm

Books_Free_Online

C++

database

Linux

Linux shell

linux socket

misce

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

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)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一区二区三区回区在观看免费视频| 国产亚洲欧美在线| 亚洲国产欧美一区| 免费一级欧美片在线播放| 亚洲电影在线| 亚洲国产精品久久久| 欧美成人精品福利| 宅男精品视频| 亚洲欧美国产不卡| 国产一区视频网站| 欧美福利一区二区| 欧美日韩国内| 欧美一区二区三区免费视| 欧美在线观看视频| 亚洲黄色在线视频| 亚洲精品影院在线观看| 国产精品普通话对白| 久久欧美肥婆一二区| 免费观看成人鲁鲁鲁鲁鲁视频| 9久re热视频在线精品| 亚洲一区欧美| 亚洲高清视频一区二区| 亚洲另类黄色| 国产一区二区三区高清| 欧美激情免费在线| 国产精品亚洲激情| 亚洲国产精品va在线看黑人| 国产精品啊v在线| 美女久久一区| 国产精品久久777777毛茸茸| 玖玖在线精品| 国产精品99免视看9| 久久亚洲精品一区二区| 欧美日韩一区在线视频| 久久综合99re88久久爱| 欧美四级电影网站| 欧美国产精品日韩| 国产伦精品一区二区三| 亚洲黄色免费| 激情综合网激情| 亚洲视频中文| 亚洲精品韩国| 久久久久国产精品一区| 亚洲在线视频一区| 欧美成人精品不卡视频在线观看| 久久精品一区中文字幕| 欧美日韩成人在线| 欧美二区乱c少妇| 国产亚洲一区二区三区| 国产精品99久久久久久久vr| 亚洲精选在线观看| 久久中文字幕一区二区三区| 欧美专区在线| 国产精品丝袜xxxxxxx| 91久久精品www人人做人人爽| 伊人蜜桃色噜噜激情综合| 亚洲永久精品国产| 亚洲欧美日产图| 欧美日韩一卡| 亚洲精品系列| 一区二区日韩免费看| 欧美成人网在线| 亚洲第一区在线| 亚洲国产三级| 欧美v国产在线一区二区三区| 久久综合999| 一区二区在线不卡| 狂野欧美激情性xxxx| 欧美bbbxxxxx| 午夜精品成人在线| 午夜精品一区二区三区在线视| 欧美午夜欧美| 亚洲影视九九影院在线观看| 性欧美videos另类喷潮| 国产精品专区第二| 欧美在线你懂的| 久久综合色综合88| 尤妮丝一区二区裸体视频| 久久永久免费| 亚洲片区在线| 亚洲欧美在线免费| 国产主播一区二区| 麻豆9191精品国产| 亚洲国内欧美| 亚洲专区免费| 欧美精品在线视频| 亚洲国产裸拍裸体视频在线观看乱了中文 | 欧美不卡激情三级在线观看| 国产在线一区二区三区四区| 欧美影院午夜播放| 久久免费国产| 最新亚洲激情| 欧美黄色一区二区| 日韩视频免费在线| 亚洲欧美一级二级三级| 欧美午夜免费影院| 亚洲综合色视频| 久久久久国产一区二区| 精品成人国产| 欧美激情一区二区三区在线视频观看| 91久久久亚洲精品| 亚洲免费在线看| 欧美日韩精品欧美日韩精品| 亚洲欧美一区二区精品久久久| 久久九九久精品国产免费直播| 精品96久久久久久中文字幕无| 美女成人午夜| 亚洲深夜福利视频| 久久夜色精品国产噜噜av| 亚洲国产导航| 国产精品日韩久久久| 久久久国产一区二区| 亚洲第一在线综合网站| 亚洲一区二区在线观看视频| 国外成人在线视频| 欧美日韩国产色综合一二三四| 亚洲中字在线| 亚洲区免费影片| 久久国产天堂福利天堂| 最新精品在线| 国产视频丨精品|在线观看| 蜜桃av一区二区| 亚洲欧美日韩中文在线制服| 久久免费的精品国产v∧| 亚洲欧美激情四射在线日| 国内视频精品| 欧美视频在线观看免费| 久久人人97超碰人人澡爱香蕉| 亚洲午夜精品网| 91久久综合亚洲鲁鲁五月天| 午夜亚洲精品| 亚洲视频精选| 亚洲人成7777| 亚洲三级毛片| 91久久精品国产| 久久亚洲二区| 久久黄色级2电影| 亚洲一区久久久| 亚洲免费电影在线观看| 亚洲国产电影| 黄色国产精品| 国产日韩在线播放| 欧美日韩在线另类| 欧美激情一区二区三区蜜桃视频 | 一区二区av在线| 亚洲国产成人午夜在线一区| 国产一区二区三区av电影| 国产精品久久久久7777婷婷| 欧美精品videossex性护士| 久久婷婷久久| 亚洲在线播放电影| 亚洲一区免费看| 制服丝袜亚洲播放| 一本色道久久88综合亚洲精品ⅰ | 亚洲一区二区三区视频| 亚洲国产欧美一区| 亚洲精品久久久久久久久久久久| 一区二区三区亚洲| 一区二区亚洲欧洲国产日韩| 国产亚洲永久域名| 国产亚洲一本大道中文在线| 国产亚洲欧洲997久久综合| 欧美性猛片xxxx免费看久爱| 国产精品美女主播| 国产区亚洲区欧美区| 欧美日本一道本在线视频| 欧美特黄一级| 国产精品日韩久久久| 国产精品视频免费观看www| 国产麻豆一精品一av一免费| 国产欧美精品在线| 国产日韩av一区二区| 在线观看不卡av| 亚洲高清一二三区| 亚洲精品永久免费| 亚洲午夜激情网页| 性娇小13――14欧美| 久久久福利视频| 久久久久九九视频| 欧美国产精品v| 亚洲作爱视频| 欧美在线影院| 欧美成人小视频| 欧美激情视频给我| 国产三级精品三级| 亚洲福利视频网站| 中文网丁香综合网| 久久精品99国产精品| 免费91麻豆精品国产自产在线观看| 亚洲国产一区二区精品专区| 亚洲视频香蕉人妖| 久久久99精品免费观看不卡| 欧美成人国产一区二区| 国产精品久久久久久久一区探花 | 亚洲一级黄色av| 欧美国产日本| 99香蕉国产精品偷在线观看| 欧美一区影院| 欧美不卡在线视频| 欧美日韩小视频|