国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 输出单链表中倒数第k个结点

输出单链表中倒数第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样的,只是我们通经常使用到的单链表都是带头结点而已。

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生