首页 » C++ » 链表中倒数第k个节点

链表中倒数第k个节点

2016-03-13 22:40:09阅读(247)

为了实现只遍历一次链表的目标,使用两个指针,第一个指针从链表头开始向前遍历走k-1步,第二个指针保持不动,从第k步开始,两个指针一起走,两个指针之间的距离保持在k-1,当第一个指针到达链表的尾部时,第二个指针正好在链表的倒数第k个节点位置。

#include<iostream>
using namespace std;

struct ListNode
{
	int m_nKey;
	ListNode *m_pNext;
};

void AddToTail(ListNode** pHead, int value)
{
	ListNode* pNew = new ListNode();
	pNew->m_nKey = value;
	pNew->m_pNext = NULL;
	if (*pHead == NULL)
		*pHead = pNew;
	else
	{
		ListNode* pNode = *pHead;
		while (pNode->m_pNext != NULL)
			pNode = pNode->m_pNext;
		pNode->m_pNext = pNew;
	}
}

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
	ListNode* pAhead = pListHead;
	ListNode* pBehind = NULL;
	for (int i = 0; i < k - 1; i++)
		pAhead = pAhead->m_pNext;
	pBehind = pListHead;
	while (pAhead->m_pNext != NULL)
	{
		pAhead = pAhead->m_pNext;
		pBehind = pBehind->m_pNext;
	}
	return pBehind;
}

int main()
{
	ListNode* pHead = NULL;
	for (int i = 0; i < 10; i++)
		AddToTail(&pHead, i);
	ListNode* pNode=FindKthToTail(pHead, 5);
	cout << pNode->m_nKey << endl;
}


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹