文章
79
粉丝
0
获赞
0
访问
3.4k
1)使用两个指针*p和*q,因为不知道链表长度,先将q向前移动k位,后面的p和q则同步每次向后移动一位结点。当q达到最后一个结点的时候,p指向的则是倒是第k个结点。
2)
1. 创建两个指针p和q,q用来先遍历,p用来指向倒数第k个。
2. 用循环先让q向前k步,如果q在走k步前就结束了,说明这个链表长度小于k,直接返回0表示失败。然后后面再一个循环,当q->link不为空的时候,p和q同时向后。
3. 当q->link为空,遍历结束。p指向的就是倒数第k个。取出那个结点的值并输出,返回1.
3)
int searchK(LList &list, int K){
LNode *p=list->link, *q=list->link;
for(int i = 0; i<k; i++){ //前进k步
if(q) q=q->link;
else return 0;
}
while(q){
p=p->link;
q=q->link;
}
printf("%d",p->data);
return 1;
}
评分及理由
(1)得分及理由(满分5分)
得分:5分
理由:学生的基本设计思想描述清晰准确,与标准答案一致。使用两个指针p和q,先让q向前移动k位,然后p和q同步移动,当q到达链表末尾时p指向倒数第k个结点。这是一趟扫描的高效算法。
(2)得分及理由(满分5分)
得分:5分
理由:学生的详细实现步骤描述完整,包含了指针初始化、q先移动k步的循环、p和q同步移动的循环、边界条件判断等关键步骤,与标准答案思路一致。
(3)得分及理由(满分5分)
得分:4分
理由:代码整体逻辑正确,但存在一个逻辑错误:在while循环中,当q为NULL时,p指向的实际上是倒数第k+1个结点,而不是倒数第k个结点。正确的做法应该是当q->link不为空时继续循环,或者调整指针初始位置。此外,代码中使用了"LList"类型,可能是识别错误,不扣分。
题目总分:5+5+4=14分
登录后发布评论
暂无评论,来抢沙发