输入一个链表,输出该链表中倒数第k个结点。
思路1:一次循环得到节点的个数,然后使用节点的个数减去倒数的k,就得到了正数的第count-k个,返回这个节点就可以了。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead==NULL || k <= 0)
{
return nullptr;
}
ListNode* pList1=pListHead;
int count=0;
int index=0;
while(pList1 != NULL)
{
count++;//记录链表节点的个数
pList1=pList1->next;
}
if(count > k)//
{
index = count-k;//找到倒数第K个节点
}
pList1=pListHead;
while(index)
{
pList1=pList1->next;
index--;
}
if(count > k)
{
return nullptr;
}
cout<<pList1->val;
return pList1;
}
};
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为16.67%
上面的程序有点问题,需要后续再改
思路二:使用跟随指针
一开始两个指针p1和p2都指向头结点,
让p1向前走k-1个节点,然后p2开始跟着p1向后跑
等p1跑到最后一个节点时,p2正好在倒数第K个节点处。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead==NULL || k <= 0)
{
return nullptr;
}
int count=0;
int a=k;
ListNode* pList1=pListHead;
ListNode* pList2=pListHead;
while(pList1 != NULL)
{
pList1 = pList1->next;
if(k<1)
{
pList2=pList2->next;
}
count++;
if(k>0)
{
k--;
}
}
if(count<a)
return nullptr;
return pList2;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)