程序员人生网站导航

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

栏目：php教程时间：2015-03-03 08:40:15

题目：输入带头结点的单链表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样的，只是我们通经常使用到的单链表都是带头结点而已。

------分隔线----------------------------

上一篇 World Wind Java开发之十――AnalyticSurface栅格渲染

下一篇 [置顶] 我到底要选择一种什么样的生活方式，度过这一辈子呢：人生自由与职业发展方向(下)

------分隔线----------------------------