《剑指offer》面试题 22：链表中倒数第k个结点（C++实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《剑指offer》面试题 22：链表中倒数第k个结点（C++实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含902字，纯文字阅读大概需要2分钟。

内容图文

题目

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

代码

#pragma once

// 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，
// 本题从1开始计数，即链表的尾结点是倒数第1个结点。

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

/**
 * 采用 两个辅助指针 
 * 走k-1步 然后两个一起走
 */

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)	// 总节点数可能不大于k
			pAHead = pAHead->m_pNext;
		else
			return nullptr;
	}

	pBehind = pListHead;
	while (pAHead->m_pNext != nullptr)
	{
		pAHead = pAHead->m_pNext;
		pBehind = pBehind->m_pNext;
	}

	return pBehind;
}

 

内容总结

以上是互联网集市为您收集整理的《剑指offer》面试题 22：链表中倒数第k个结点（C++实现）全部内容，希望文章能够帮你解决《剑指offer》面试题 22：链表中倒数第k个结点（C++实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---