CCI习题2-2:nTh From the last

By | 2012 年 11 月 14 日

画一个链表出来,实际看看就知道怎么写了。
用一个pointer pRun在前面从pHead先跑n个位置。(如果中途为NULL,说明输入的数大于了链表长度)
然后用另一个pointer pCur从pHead开始,和pRun同步往后跑,直到pRun为NULL,这个时候返回pCur就可以了。



题目
Implement an algorithm to find the nth to last element of a singly linked list.



代码,只贴主要部分,用到的其它辅助函数和Node结构参见2-1

<

pre>
//zero based n th from the rear
Node * nThFromLast(Node *pHead, int n) {
if (n < 0) {
cout<<“n below 0″<<endl;
return NULL;
}
Node *pCur = pHead;
Node *pRun = pHead;
//1.let pRun go n position before pCur
for (int i = 0; i <= n; ++i) {
if (!pRun) {
cout<<“Not enough nodes”<<endl;
return NULL;//no enough nodes in the link list
}
pRun = pRun->next;
}
//2.go paralell untile pRun become NULL
while (pRun) {
pRun = pRun->next;
pCur = pCur->next;
}
return pCur;
}
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”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
Node *pNth = nThFromLast(phead,10);//test 10,9,5,1,0,12,-11
if (pNth) {
cout<value<<endl;
}
cout<<“done”<<endl;
return 0;
}

发表评论

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