面试题22:链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个结点。
思路在代码里面有,这里主要讲注意代码的鲁棒性,注意异常情况:
- 若输入的链表为空;
- 若输入的<=0;
- 若链表长度小于k.
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { //处理异常情况1,2 if (pListHead == nullptr||k<=0) return nullptr; ListNode* p1 = pListHead, * p2 = pListHead; int i = 1; //p1走到k-1个位置 while (i<k) { p1 = p1->next; i++; //处理异常情况3 if (p1 == nullptr) { return nullptr; } } //p1与p2同步向后遍历,直至p1走到末端,p1所指即为倒数第k个节点 while (p1->next!=nullptr) { p1 = p1->next; p2 = p2->next; } return p2; }