输出单链表中倒数第k个结点

题目:输入带头结点的单链表L,输出该单链表中倒数第k个结点。单链表的倒数第0个结点为该单链表的尾指针。要求只能遍历1次单链表。


解题思路:
如果不要求只能遍历1次单链表,我们可以先遍历1次单链表,求出它的结点的总个数n(包括头结点),所以单链表的结点是从倒数第n⑴个到倒数第0个,然后再遍历1次单链表,遍用时访问的第n-k⑴个结点就是该单链表中倒数第k个结点。现在要求只能遍历1次单链表,可以设两个指针p和q,最开始时它们都指向头结点,然后p向后移动k位,最后p,q同时向后移动直到p为最后1个结点,那末此时q即为所求。


ADT定义以下
#define ElemType int
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode,*LinkList;


算法实现:

LNode* reciprocalKNode(LinkList &L,int k)
{
if(k<0) {
printf("k不可以为负数");
return NULL;
}
if(L==NULL)
{
printf("单链表为空");
return NULL;
}
LNode* p=L;
LNode* q=L;
while(k>0)
{
p=p->next;
if(p==NULL)
{
printf("单链表太短,不存在倒数第k个结点");
return NULL;
}
}
while(p->next!=NULL)
{
p=p->next;
q=q->next;
}
return p;
}

PS:这1题对不带头结点的单链表的解法是1模1样的,只是我们通经常使用到的单链表都是带头结点而已。

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 输出单链表中倒数第k个结点

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡