两道笔试题

昨天一朋友找工作, 碰到两道算法笔试题, 都是当于链表操作的.

原题具体的还原不过来了, 不过大致是:

1. 有一单链表, 找出最后第m个节点.

 昨天看到问题时,想到了小学应用题:

汽车过山洞, 假如这个汽车开着开着, 等到车头刚要出山洞, 车尾离山洞出口也有一段距离嘛...

这样, 这个题方法出来了


当然,特殊情况要考虑, 不过那....


2.  有一单链表, 判断是否存在环

 
有环? 走着走着, 却突然发现, 怎么也走不完, 可是这要走到什么时候? 此法不通

可是怎么也想不出好办法. 只有一个笨方法:

看看现在走的路, 是不是已走过...



对于2, 不知道有没有更好的办法?

one = root
two = root 
two.next; （刚刚忘记先走出去一步了）
    while (one.next) {// 1号，走一站
        two.next; // 2号，走1站，（比one快一步）
         if(two==one) return true;// 看是否与1号相遇 
        two.next;//2号，再走一站，（比one快二步）
          if(tw0==one)return true;
   
     }  
return false;

上学时一个例题？？？大约是这么写的，几乎没写过C

第2题，在单链表的情况下应该是只有这个方法了吧。时间复杂度也不高，

第2题应该把走过的node记录下来，查找快点。

bool hasCycle(node* p){
set<node*> passed;

while( p->next){
p= p->next;
if( passed.find(p) != passed.end()) return true;
passed.insert(p);
}
return false;

特殊情况没有考虑。