# CCI题目2-5：Find Loop

By | 2012 年 11 月 16 日

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>
map exmap;
}
}
return NULL;
}

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
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”;
cout<<“process…”<<endl;
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);
}
```