大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 题目：链表的倒数第K个结点
题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。
二 解题思路
抛开常规解法，采用只遍历一次就能找到倒数第k个结点，可以定义两个指针：
（1）第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；
（2）从第k步开始，第二个指针也开始从链表的头指针开始遍历；
（3）由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
三 代码实现
template <typename T> struct Node { public: T data; Node *pNext; }; template <typename T> class ListEx { private: Node<T> *m_pHead; Node<T> *m_pTail; public: ListEx() { m_pTail = m_pHead = NULL; } ~ListEx() { Node<T> *pTemp = NULL; Node<T> *pNode = m_pHead; while (pNode) { pTemp = pNode; pNode = pNode->pNext; delete pTemp; } m_pHead = m_pTail = NULL; } void add(T data) { Node<T> *pNode = new Node<T>; pNode->data = data; pNode->pNext = NULL; if (m_pHead == NULL) { m_pTail = m_pHead = pNode; } Node<T>* pTemp = m_pTail; pTemp->pNext = pNode; m_pTail = pNode; } Node<T> *GetListHead() { return m_pHead; } }; // 链表的倒数第k个结点，注意倒数从1开始 template <typename T> Node<T>* FindKthToTail(Node<T> *pNode, int k) { // k必须不大于Node的结点数目 if (!pNode || k < 0) return NULL; Node<T> *p1 = pNode; Node<T> *p2 = pNode; int nIndex = 0; bool bStart = false; int nFalg = 0; while (NULL != p2->pNext) { if (nIndex == k-1) { bStart = true; } if (bStart) { p1 = p1->pNext; } p2 = p2->pNext; nIndex ++; } return p1; } void main() { ListEx<int> *pList= new ListEx<int>(); pList->add(1); pList->add(2); pList->add(3); pList->add(4); pList->add(5); pList->add(6); pList->add(7); Node<int> *pHead = pList->GetListHead(); Node<int> *pNode = FindKthToTail(pHead, 2); cout << pNode->data <<endl; pNode = FindKthToTail(pHead, 1); cout << pNode->data <<endl; pNode = FindKthToTail(pHead, 7); cout << pNode->data <<endl; delete pList; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120162.html原文链接：https://javaforall.net
