题目要求:
输入一个链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
参考资料:剑指offer第15题
题目分析:
1.两个指针,第一个先走k步,然后两个指针同时走,直到第一个走到尾指针,此时第二个指针即为所求;
2.令函数原型为:ListNode *findKthToTail(ListNode *head,unsigned int k);
特殊情况:
i). head为空指针;
ii). head为头结点的链表的结点总数小于k;
iii).k=0.
3.注意此处为倒数第0个结点为链表的尾结点,与剑指offer的第一个结点的区别是:第0个结点的最后一个while里应该ptwo->next != NULL;而第1个结点的最后一个while里应该ptwo != NULL。可画图理解。
代码实现:
#include <iostream> using namespace std; typedef struct ListNode { struct ListNode *next; int data; }ListNode; ListNode *findKthToTail(ListNode *head,unsigned int k); void initList(ListNode **head); int main(void) { // int k = 4; int k = 1; ListNode *head; initList(&head); head = findKthToTail(head,k); if(head==NULL) cout << "head为空或者链表长度小于k"; else cout << head->data << " "; cout << endl; return 0; } ListNode *findKthToTail(ListNode *head,unsigned int k) { if(k==0 || head==NULL) return NULL; ListNode *pone,*ptwo; pone = ptwo = head; for( ; k > 0 && ptwo != NULL; k--) ptwo=ptwo->next; if (k > 0) return NULL;//链表长度小于k while(ptwo->next != NULL) { pone=pone->next; ptwo=ptwo->next; } return pone; } //1-->2-->3-->NULL void initList(ListNode **head) { ListNode *tmp = new ListNode; tmp->data = 1; *head = tmp; tmp = new ListNode; tmp->data = 2; (*head)->next = tmp; ListNode *tmp1 = new ListNode; tmp1->data = 3; tmp1->next = NULL; tmp->next = tmp1; }