[华为]输出单向链表中倒数第k个结点
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
详细描述：
接口说明
原型：
ListNode* FindKthToTail(ListNode* pListHead, unsignedint k);
输入参数：
ListNode* pListHead单向链表
unsigned int k倒数第k个结点
输出参数（指针指向的内存区域保证有效）：
无
返回值：
正常返回倒数第k个结点指针，异常返回空指针
输入描述:
输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值
输出描述:
输出一个整数
输入例子:
8
1 2 3 4 5 6 7 8
4
输出例子:
5
//利用两个指针遍历找到链表的倒数第K个元素
#include<iostream>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int a)
{
val=a;
next=NULL;
}
};
ListNode *findKth(ListNode *head,int k)
{
if(k<1) return NULL;
ListNode *p1 = head;
ListNode *p2 = head;
for(int i = 0; i<k-1; i++)
{
p1 = p1->next;
}
while(p1 !=NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
int main()
{
int n;
while(cin>>n)
{
int val;
ListNode *head = new ListNode(0);
ListNode *p = head;
for(int i = 0; i<n; i++)
{
cin>>val;
ListNode *q = new ListNode(val);
p->next = q;
p = p->next;
}
int k;
cin>>k;
ListNode *temp = findKth(head,k+1);//本题的特殊之处，存在倒数第0个
cout<<temp->val<<endl;
}
return 0;
}
页:
[1]