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 阅读(1805) 评论(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;

}
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

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

搜索

  •  

最新评论

阅读排行榜

评论排行榜