输出单链表中倒数第k个结点
来源:程序员人生 发布时间:2015-03-03 08:40:15 阅读次数:2769次
题目:输入带头结点的单链表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样的,只是我们通经常使用到的单链表都是带头结点而已。
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠