快慢指针可以做到一次遍历,需要返回倒数第k个节点,我们可以看做当快指针now指向链表末尾的nullptr时,慢指针bef正好指向倒数第k个节点,所以需要一开始先让快指针now移动k个节点。
为了方便处理,设置一个dummyhead作为伪头节点,bef和now都从dummyhead出发。
因为样例中存在k越界的情况,针对这部分需要加入条件额外判断。
class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (!pListHead) return nullptr; if (k <= 0) return nullptr; ListNode* dummyhead = new ListNode(0); dummyhead->next = pListHead; ListNode* bef = dummyhead, *now = bef; for (int i = 0; i < k && now; i++) { now = now->next; } while (now) { now = now->next; bef = bef->next; } return bef == dummyhead? nullptr: bef; } };