题目描述
输入一个链表,输出该链表中倒数第k个结点。
思路一:链表不能向前遍历,只能向后遍历。因此倒数第K个结点就是 正序的 :len(链表)-1-K的下一个。 注意,此处的思路与代码中具体实现有点不同,但是 是一致的。假设用i=0计数,那么应该就是i<len(链表)-k 或者 i<=len(链表)-k-1. 下列代码中是设置i=1开始,那么应该就是 i<len(链表)-k+1 或者 i<=len(链表)-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) {
int len=0;
ListNode *p=pListHead;
while(p!=NULL) {
len++;//算出链表长度
p=p->next;
}
if(k>len || k<0) return NULL;//两种特殊情况
int i=1; //设置一个变量
p=pListHead;//p重置为起点
while(i<len-k+1) {//直到整数第len(list)-k个位置,进行最后一层循环,到达
p=p->next;
i++;
}
return p;
}
};
http://blog.csdn.net/hhh3h/article/details/20832387
另一种思路:
class Solution {
public:
ListNode* FindKthToTail(ListNode* p_head, unsigned int k)
{//找到链表的倒数第K个节点
//if(k==0)特殊处理,k小于链表长度,特殊处理
if (k==0 || p_head == nullptr)
return nullptr;
ListNode* first = p_head;
ListNode* second = p_head;
for (int i = 0; i < k - 1; i++) {
if(first->next== nullptr) return nullptr;
first = first->next;
}
while (first->next != nullptr)
{
first = first->next;
second = second->next;
}
return second;
}
};