假设链表总共有n个节点，那么倒数第k个节点就是正数第n-k+1个节点。为了得到n，需要遍历一次链表，这样就需要遍历链表两次。
为了实现遍历一次链表就得到倒数第k个节点，可以定义两个指针，第一个指针从头指针开始先向前走k-1步，第二个指针保持不动；从第k步开始，两个指针同步向前移动，当第一个指针到达尾节点时，第二个指针恰好位于倒数第k个节点处。
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (pListHead == nullptr || k == 0) return nullptr; ListNode *pAhead = pListHead; ListNode *pBehind = nullptr; for (unsigned int i = 0; i < k - 1; ++i) { if (pAhead->m_pNext != nullptr) pAhead = pAhead->m_pNext; else { return nullptr; } } pBehind = pListHead; while (pAhead->m_pNext != nullptr) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind; }
ListNode* FindMidNode(ListNode* pListHead) { if (pListHead == nullptr) return nullptr; ListNode* pSlow = pListHead; ListNode* pFast = pListHead; while (pFast!=nullptr && pFast->m_pNext!=nullptr) { pSlow = pSlow->m_pNext; pFast = pFast->m_pNext->m_pNext; } return pSlow; }
原文：https://www.cnblogs.com/larry-xia/p/10665241.html