寻找链表的倒数第k个节点

题目：已知一个带有表头结点的单链表，节点结构为（data，next），假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的节点（k为正整数），若查找成功，返回指向该节点的指针；否则，返回nullptr。

解法：设置两个指针p1，p2同时指向单链表的表头，令p2向后移动k个节点。下图为k=3的情况

之后同步向后移动p1和p2，当p2为nullptr的时候，p1即为所求。

代码：

struct Node

{

	int data;

	Node* next;

};

using List = Node*;

Node* locateNodeFromBottom(List l, int k)

{

	Node* p1 = l;

	Node* p2 = l;

	//p2向后移动k步

	for (int step = 0; step < k && p2 != nullptr; ++step)

		p2 = p2->next;

	//若链表长度小于k，则返回nullptr

	if (nullptr == p2)

		return nullptr;

	//同步移动p1和p2，当p2为nullptr时，p1即为所求

	while (p2 != nullptr)

	{

		p2 = p2->next;

		p1 = p1->next;

	}

	return p1;

}

时间复杂度：该算法只遍历了一次链表，故算法的时间复杂度为O(n)

巴特西

寻找链表的倒数第k个节点

寻找链表的倒数第k个节点

最新文章

热门文章