两道笔试题

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

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

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

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

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

这样, 这个题方法出来了

cpp 代码

Node* FindLastNode(Node* root, int m) {
    Node* head = root;
    Node* tail = root;

    // 开始时,大概是这样
    //           |---------------------|  这个是山洞
    //           >>               这个是车车? 哦, 是小蛇, 身体盘在一起...

    // 然后往前爬
    for (int i = 0; i < m; ++i) {
        head = head->next;
    }

    // 此时
    //           |---------------------|  这个是山洞
    //           >-------->

    // 一起前进吧
    while (head->next) {
        head = head->next;
        tail = tail->next;
    }

    // 此时
    //           |---------------------|  这个是山洞
    //                        >-------->

    return tail;
}

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


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

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

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

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

cpp 代码

bool HasCircle(Node* root) {
    Node* cur = root;
    while (cur->next) { // 1 号走到一个站， 等
        // 派出2号，开始走， 看是否更快地和1号相遇
        for (Node* other = root; other->next != cur; other = other->next) {
            if (cur->next == other) {
                return true;    // 2号提前赶到， 1 号走冤枉路了
            }
        }
        cur = cur->next;
    }
    return false;
}

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

评论

3 楼 jjcang 2007-08-17  

第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;

特殊情况没有考虑。

2 楼 bcccs 2007-08-15  

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

1 楼 抛出异常的爱 2007-08-15  

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