CCI题目2-3:Remove Node at Middle of a Link List

By | 2012 年 11 月 16 日

两个指针,一个在前面跑,一个跟在后面,前面的跑两步,后面的跑一步。最后删除后面指针指向的那个节点即可。



题目
Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e



代码

<

pre>
void RemoveMiddle(Node **ppHead) {
//1,2 del 0; 3,4 del 1; …
if (!(ppHead)) {
return;
}
Node *pRunner = (
ppHead)->next;
Node **ppPre = ppHead;
bool move = false;
while (pRunner) {
pRunner = pRunner->next;
if (move) {
ppPre = &(*ppPre)->next;
}
move = !move;
}
//hold the removing one
pRunner = *ppPre;
//delete it from list
*ppPre = pRunner->next;
//delete it
delete pRunner;
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// instr = “10,9,8,7,6,5,4,3,2,1,0”;
// instr = “0,1,2,3,4,5,6,7,8,9,10”;
instr = “”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
RemoveMiddle(&phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

发表评论

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