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

发布时间：2020-12-13 20:14:49 所属栏目：PHP教程来源：网络整理

导读：题目：输入带头结点的单链表L，输出该单链表中倒数第k个结点。单链表的倒数第0个结点为该单链表的尾指针。要求只能遍历1次单链表。解题思路：如果不要求只能遍历1次单链表，我们可以先遍历1次单链表，求出它的结点的总个数n（包括头结点），所以单链表的结

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!