CCI题目2-5:Find Loop

By | 2012 年 11 月 16 日

建一个hash来做,从前往后扫描,遇到重复的输出就可以了。(findLoop)
最后有c++中map的简单实用例子。



另外cci上写了一个更有意思的算法,就是两个指针在链表上跑,一个快一个慢,慢的跑一步,快的跑两步。
当他们相遇的时候,让快的那个到链表开头,然后两个指针以相等的速度(一比一),继续跑,再次相遇的时候就是loop的开始点。

为什么?
假设有一个n米长的环形跑道,两个人一快一慢(2:1)从同一个起点开跑。下次相遇在哪儿?起点,而且是快的跑了两圈,慢的一圈。
进一步,如果快的那个先跑了k米呢?那他们应该相遇在距起点k米的位置。因为Sl = t, Sh = 2t + k,而令Sh = Sl + pn,可以得到t = pn – k。也就是他们总会在这个位置相遇。
所以此时让快的那个回到起点,(起点正好距循环开始k米),下次相遇,就是循环开始点。
这个想法很巧(findLoopEx)



题目
Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C



代码

<

pre>
Node * findLoop(Node *pHead) {
map exmap;
while (pHead) {
if (exmap.find(pHead) != exmap.end()) {
return pHead;
}
exmap[pHead] = true;
pHead = pHead->next;
}
return NULL;
}

Node *findLoopEx(Node *pHead) {
Node *pRunner = pHead;
Node *pWalker = pHead;
int step = 0;

//each step of walker, runner goes two.
while (pRunner) {
    pRunner = pRunner->next;
    if (++step == 2) {
        pWalker = pWalker->next;
        step = 0;
        if (pRunner == pWalker) {
            break;
        }
    }
}
if (!pRunner) {
    return NULL;//no loop
}
//then they meet at the k posotion before loop started
//and the k is nodes before loop start
//so let runner back to head and with speed of 1
//they go simutaniously, when next meet, that position is the loop start point
pRunner = pHead;
while (pWalker) {
    if (pWalker == pRunner) {
        return pWalker;
    }
    pWalker = pWalker->next;
    pRunner = pRunner->next;
}
return NULL;//something wrong

}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
Node *phead = loopList(10, 8);
printList(phead);
cout<<“process…”<<endl;
Node *pLoop = findLoop(phead);
printList(pLoop);
cout<<“done”<<endl;
return 0;
}



map操作

void mapTest(){
    map testmap;
    //insert key,val in map:
    testmap[1] = true;
    testmap[666] = false;
    //find key in map
    map::iterator it = testmap.find(1);
    if (it != testmap.end()) {
        //key if found in map
        int key = it->first;//this is key
        bool val = it->second;//this is val;
        it->second = !val;
    }
    //delete a key
    testmap.erase(1);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注