一个关于单向链表的面试题。

yuephone

可不可以用地址来判断呀!
取指针指向的地址来进行对比,我感觉挺直观的

Michaelgs

时间复杂度O(n)，空间复杂度O(1)， 方法如下：

设环的长度为Y
用两个步长分别为1和2的指针前进，第一次相遇之后再前进，第二次相遇时停止。
记下从第一次相遇到第二次相遇，步长为1的指针走过的步数S，则S＝＝Y。环的长度就知道了

用两个指针，一个在链头，一个走到链头后第Y个位置上
判断两个指针是否相等，如果是就是环的起始位置了
否则两个指针各自前进一步，再判断

goldensunflower

学习了

lishenyu

2003至2010年国家公务员考试形势分析
2010年国家公务员面试分数线已经公布，中公教育的考试研发专家第一时间就2003年—2010年的面试情况进行了深入分析，给进入面试的各位考生提供应试参考。
从上表中可以看出，2003年共有5400个招考职位，招录5475人，基本上是“一个萝卜一个坑”。到了今年，招录职位已经扩充到了9275个，招录人数也达到了15526，招录职位将近是2003年的2倍，招录人数是2003年的3倍，职位与人数的比例达到了1：1.67，这一比列大大超过2003年的比例。

　　这样的比例客观上说，大大提高了录取的比例，也是驱使公务员考试一年热似一年的原因之一。
通过上表的分析，我们可以看出，从2003年—2010年无论审核通过的人数还是实际参考的人数都在逐年上涨，而且这种上涨趋势极其猛烈。从中可以得出如下几点结论：

　　第一，国家公务员考试竞争确实越来越激烈。原本只有12.5万人参加的公务员考试，经过八年，这个人数就涨到了146万。

　　第二，“跟风者”众多。2003年时，弃考者有4万人，约占审核通过人数的三分之一；2010年弃考者有40万，也是约占审核通过人数的三分之一。

　　中公教育专家提醒，考生切勿被巨大的审核通过人数和实际参考人数吓倒，毕竟真正有实力的人，是不会被埋没的。
液位开关
料位开关
料位计
气动敲击锤
液位变送器
电缆浮球液位开关
侧装浮球液位开关
连杆浮球液位开关
小型浮球液位开关
射频电容液位开关
射频电容料位开关
阻旋式料位计
阻旋料位开关

浮球液位计窦智开
液位计
浮球式液位开关
浮球液位开关
上海液位开关
浮球连续式水位计
友情链接：浮球连续式液位计
阻旋料位计
阻旋物位开关
侧装浮球开关
浮球开关
液位变送器
阻旋式料位开关
射频电容液位计
射频电容料位计
射频导纳液位开关
射频导纳料位开关
射频导纳液位计
射频导纳料位计
投入式液位计
投入式液位开关
阻移式料位计
阻移式料位开关
电容式液位计
电容式液位开关
电缆浮球开关

上海物流
上海货运出租车
上海物流快运
上海物流货运
友情链接：上海物流专线


阻旋式料位变送器
阻旋式物位变送器
友情链接：射频导纳液位指示计
射频导纳液位指示器
射频导纳料位指示计
射频导纳料位指示器
浮球连续式液位开关
浮球连续式液位变送器

benjiam

很简单
1=>2=>3=>4=>5=>6=>3
a    b                                

循环
for (; ; b = b->next)
{
  for (x = a; x != b; x++)
{
     if (x == b->next)
    {
          print(x);
          return;
    }
}
}


哪来那么多 2步 1步的问题？

又不是判定是不是循环

JohnBull

用hash表?

hp_truth

大家都是牛人， 让新人受益良多。

今天看到关于单向链表的这个两个帖子， 觉得很有收获， 自己参考各位的想法写了一个小程序， 以后得多向各位学习。

按照版主的想法,  大体思路是： 在判断是否有环路时， 我们可以得到相遇的节点， 计为M。 然后我们可以从头部节点H开始遍历，直到这个遇到M， 这个距离算作i； 我们也可以计算从M节点开始，绕环再走一圈(重新回到M)的距离， 计为j。

然后让指针P1指向H， P2指向M, 如果i>j, 则让P1先往前走(i-j)步; 如果j>i,则让P2往前走(j-i)步.
接下来, P1和P2 同时往前走, 它们必然相遇于环的第一个节点.

1. 
   
2. #include        <stdio.h>
   
3. #include        <stdlib.h>
   
4. 
   
5. struct list {
   
6.     int data;
   
7.     struct list * next;
   
8. };
   
9. 
   
10. // judge if the list has a loop
    
11. int has_loop (struct list *head, struct list **meeting_node) {
    
12.     int step1 = 1, step2 = 2;
    
13.     struct list *p1 = head, *p2 = head;
    
14.     int i;
    
15. 
    
16.     while ( p1 != NULL ) {
    
17.         for (i=0; i!=step1; ++i) {
    
18.             p1 = p1->next;
    
19.         }
    
20.         for (i=0; i!=step2; ++i) {
    
21.             p2 = p2->next;
    
22.             if (p2 == NULL)
    
23.                 return 0;
    
24.         }
    
25.         printf ("p1->data = %d, p2->data = %d\n", p1->data, p2->data);
    
26.         if ( p1 != NULL && p1 == p2 ) {
    
27.             *meeting_node = p1;
    
28.             return 1;
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }
    
33. 
    
34. struct list * first_node_of_loop(struct list *h) {
    
35.     struct list *meeting_node = NULL;
    
36.     struct list *p1 = h, *p2 = h;
    
37.     int i, j, k;
    
38.     if (!has_loop(h, &meeting_node)) {
    
39.         return NULL;
    
40.     }
    
41. 
    
42.     printf("meeting_node: %d\n", meeting_node->data);
    
43.     // how long from head node to meeting_node
    
44.     i = 0;
    
45.     while (p1 != meeting_node) {
    
46.         ++i;
    
47.         p1 = p1->next;
    
48.     }
    
49.     // how long of the loop
    
50.     j = 1;
    
51.     p2 = meeting_node->next;
    
52.     while (p2 != meeting_node) {
    
53.         ++j;
    
54.         p2 = p2->next;
    
55.     }
    
56. 
    
57.     printf("i=%d, j=%d\n", i,j);
    
58.     // let them start at the same distance away from meeting_node
    
59.     p1 = h;
    
60.     p2 = meeting_node;
    
61.     if (i > j) {
    
62.         k = i - j;
    
63.         while(k-- > 0) {
    
64.             p1 = p1->next;
    
65.         }
    
66.     }
    
67.     else {
    
68.         k = j - i;
    
69.         while(k-- > 0) {
    
70.             p2 = p2->next;
    
71.         }
    
72.     }
    
73. 
    
74.     // now they are at the same distance away from meeting_node,
    
75.     // let them move on until they meet at the initial_node_of_loop
    
76.     while (p1 != p2) {
    
77.         p1 = p1->next;
    
78.         p2 = p2->next;
    
79.     }
    
80.     return p1;
    
81. }
    
82. 
    
83. void print_list (struct list *h) {
    
84.     int cnt = 0;
    
85.     int max_step = 25;
    
86.     while ( h != NULL ) {
    
87.         printf("%d  ", h->data);
    
88.         h = h->next;
    
89.         // to prevent infinite loop
    
90.         if (++cnt > max_step) {
    
91.             printf("\n");
    
92.             return;
    
93.         }
    
94.     }
    
95.     printf("\n");
    
96. }
    
97. 
    
98. // add a new node to the existing list
    
99. void add_to_list(struct list ** ph, int d) {
    
100.     struct list *p = malloc(sizeof(struct list));
     
101.     if (p == NULL) {
     
102.         printf("malloc failed\n");
     
103.         abort();
     
104.     }
     
105.     p->data = d;
     
106.     p->next = NULL;
     
107. 
     
108.     if ( *ph == NULL ) {
     
109.         *ph = p;
     
110.         return;
     
111.     }
     
112. 
     
113.     struct list *h = *ph;
     
114.     while ( h->next != NULL) {
     
115.         h = h->next;
     
116.     }
     
117.     h->next = p;
     
118. }
     
119. 
     
120. // let the tailer of the list point to the nth node
     
121. void create_loop (struct list *h, int n) {
     
122.     struct list *p = h;
     
123.     struct list *n_node = h;
     
124.     int i = 1;
     
125.     while ( p->next != NULL ) {
     
126.         p = p->next;
     
127.         if (++i == n) {
     
128.             n_node = p;
     
129.         }
     
130.     }
     
131.     p->next = n_node;
     
132. }
     
133. 
     
134. 
     
135. int main ( int argc, char *argv[] )
     
136. {
     
137.     // create a list
     
138.     struct list *head = NULL;
     
139.     struct list *meeting_node = NULL;
     
140.     int i;
     
141.     for (i=1; i!=10; ++i)
     
142.         add_to_list(&head, i);
     
143. 
     
144.     print_list(head);
     
145. 
     
146.     if (has_loop(head, &meeting_node)) {
     
147.         printf("has loop at node: %d\n", meeting_node->data);
     
148.     }
     
149.     else {
     
150.         printf("has no loop\n");
     
151.     }
     
152. 
     
153. 
     
154.     // create a loop in the list
     
155.     create_loop(head, 2);
     
156. 
     
157.     print_list(head);
     
158. 
     
159.     if (has_loop(head, &meeting_node)) {
     
160.         printf("has loop at node: %d\n", meeting_node->data);
     
161.     }
     
162.     else {
     
163.         printf("has no loop\n");
     
164.     }
     
165. 
     
166.     struct list *first_node = first_node_of_loop(head);
     
167.     if (first_node) {
     
168.         printf("the first node of loop is: %d\n", first_node->data);
     
169.     }
     
170. 
     
171.     return 0;
     
172. }
     
173. 
     

复制代码

zhangsuozhu

我有三个笨办法。

一是在链表中每个结点加一个char型的标志默认置零， 每访问一个结点置1。遇到置1的，即说明已经访问过。是循环链表的头部。时间复杂度O(n),空间复杂度O(n)

二是找一个合适的值做hash.如32位系统中用指针的低16位做hash. 建立2^16 大小的hash表,。(key冲突要解决)。每访问一个结点。算出哈稀值，在hash中记录该指针。如果hash有本指针，则说明该地址该问过。即循环链表的头部。

三是一开始就让链表的Key值有序，比如从小到大。如果一个结点的下一个结点小于本结点，就可以找到循环链表的头部

zhanglistar

回复 27# emacsnw


    hash也是有冲突的呀，因为不知道链表的长度，所以hash得到的结果不一定是对的。

yeleven86

可以证明，从慢指针进入循环开始，快指针一定会在慢指针循环一圈之前与之相遇，记下相遇点为P1；
此时使P2指向链首，分别从P1和P2出发，用指针A、B遍历。
如果A先遇到P1，则将B所在点设成P2，继续遍历；
如果B先碰到P1，或一起碰到，则可知P2到P1的距离小于等于循环节点数，且P2必在循环外，或在进入循环的节点上。
此时从P1、P2出发用A、B遍历：
如果A未遇到B，则继续遍历，遇到P1时B访问下一节点；
如果A遇到B，则所遇节点即为循环入口节点。