首页 > 代码库 > C++ 算法之 链表中倒数第k个节点
C++ 算法之 链表中倒数第k个节点
题目：输入一个链表，输出链表中倒数第k个节点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾巴节点是倒数第一个节点。
方法1：先遍历链表得到链表的个数n，倒数第k个节点就是n-k+1再遍历一次链表，找到第n-k+1个节点就是倒数第k个节点；这种方法遍历两次链表；
方法2：先遍历链表把链表压入一个栈，再出栈，第k次出栈就是第k个节点；
方法3：先反转链表，再遍历
方法4：定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1；第二个指针保持不动，从第k步开始，第二个指针也开始遍历，两个指针差距k-1个距离
，当第一个指针走到了尾巴节点，第二个指针正好在倒数第k个节点；
代码：
ListNode* FindKthFromTail(ListNode* pListHead,int k){ if (pListHead == NULL || k == 0)//防止空的链表 和 k值 等于 0 的情况 { return NULL; } ListNode* pAhead = pListHead; ListNode* pBehind = NULL; for (int i = 0; i < k-1; i++) { if (pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; } else { return NULL; } } pBehind = pListHead; while(pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind;}全部完整代码：
// FindKthFromTail.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;struct ListNode { int m_nValue; ListNode* m_pNext; ListNode(int k):m_nValue(k),m_pNext(NULL) { }};ListNode* FindKthFromTail(ListNode* pListHead,int k){ if (pListHead == NULL || k == 0)//防止空的链表 和 k值 等于 0 的情况 { return NULL; } ListNode* pAhead = pListHead; ListNode* pBehind = NULL; for (int i = 0; i < k-1; i++) { if (pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; } else { return NULL; } } pBehind = pListHead; while(pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind;}int _tmain(int argc, _TCHAR* argv[]){ ListNode* head = new ListNode(1); ListNode* Node1 = new ListNode(2); ListNode* Node2 = new ListNode(3); ListNode* Node3 = new ListNode(4); ListNode* Node4 = new ListNode(5); ListNode* Node5 = new ListNode(6); ListNode* Node6 = new ListNode(7); head->m_pNext = Node1; Node1->m_pNext = Node2; Node2->m_pNext = Node3; Node3->m_pNext = Node4; Node4->m_pNext = Node5; Node5->m_pNext = Node6; Node6->m_pNext = NULL; ListNode* p = FindKthFromTail(head,3); cout<<p->m_nValue<<endl; getchar(); return 0;}
C++ 算法之 链表中倒数第k个节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。