题目:输入一个单向链表,输出该链表中倒数第 k 个结点。
传统做法是获取到链表的长度n,然后走n-k布,此方法弱爆了……
做法:
1、指定一个新的指针,走k步。如果k布之内就到了NULL,显然无倒数第k这说法,返回错误即可。
2、新指针到位后,和root一起next,知道新指针到了NULL。此时输出root指针当前的data即可。
int ll_last_k(struct Node* root, int k)
{
// Make two ptr diff k distance
struct Node* ptr = root;
for(int i=0;i<k;i++)
{
if(ptr==NULL)
{
return -1;
}
ptr = ptr->next;
}
// Both next
while(ptr!=NULL)
{
ptr = ptr->next;
root = root->next;
}
return root->data;
}