每天一算法(输出链表倒数第k个元素)
题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
思路:
题目要求输出链表倒数第K个节点,那我们就把链表反转,输出第K个节点的值就可以了。
/*-----------------------------Copyright by leeyunce. Modified by yuucyf . 2011.05.08------------------------------*/template<typename T>S_ListNode<T>* ReverseListRecursive(S_ListNode<T>* psHead){ if (!psHead|| !(psHead->m_pNext)) return psHead; S_ListNode<T>* psRet = ReverseListRecursive(psHead->m_pNext); psHead->m_pNext->m_pNext = psHead; psHead->m_pNext = NULL; return psRet;}