题目:输入一个单向链表,输出该链表中倒数第 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; }