深信服一道笔试:如何判断两个单向链表是否有相交,并找出交点。
题比较简单,单向链表有交点意思就是交点后的节点都是一样的了。
NODE* FindNode(NODE* pHead1, NODE* pHead2) { NODE* p1 = pHead1; NODE* p2 = pHead2; int i = 1, j = 1, k = 0, f = 0;
if(pHead2 == NULL || pHead2 == NULL) { return NULL; }
while(p1->next != NULL) { p1 = p1->next; i++; }
while(p2->next != NULL) { p2 = p2->next; j++; }
if(p1 != p2) { return NULL; } else { p1 = pHead1; // 1 p2 = pHead2;
f = fabs(i, j); if(i > j) // 2 { for(k=0; k<f; k++) { p1 = p1->next; } while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } else { for(k=0; k<f; k++) { p2 = p2->next; } while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } } }
|
1,在第一次遍历完链表后,进行第二次遍历,需要把指针再次初始化;看见网上一些人给的例子没有再次初始化显然是错误的;再调用NULL的next不死才怪!
2,小优化。循环和判断,把判断放在外面;如果把i和j大小判断放在里面的话就意味着循环多少次,判断就执行多少次;当然这样做的唯一不足就是代码多了点;还有for循环之前的对f的赋值,有的为了简便直接放在for语句里面,不过同样道理,放在for循环里面,就执行了n次的fabs;拿出来赋值,只赋值一次就OK。
友情提示:养成写高效代码的习惯,不能图简便,觉得代码越少就越牛!
阅读(2390) | 评论(4) | 转发(0) |