如何快速查找链表中倒数第N个节点

链表不像顺序表查找来的方便,因为链表是没有索引的。（我们使用带有头节点的链表进行讨论）

方法一：

我们可以先获取链表的长度
再找出顺须节点的位置
重新遍历统计位置匹配

缺点：查找效率低推荐

方法二：

使用俩个指针，一个快指针，一个慢指针
快的先走N步，然后快慢指针同步进行
快指针指向地址为NULL的时候就表示已经到达最后一个位置
这时候慢指针距离最后一个位置就相差N个单位

优点：查找效率高推荐

下面是使用C语言代码实现示例

//使用快慢指针
int findNode(Node*list, int pos) {
	Node *fast = list->next;//指向第一个节点
	Node *slow = list->next;
	//想让快指针走pos步
	for (int i = 0; i < pos; ++i)
	{
		/* code */
		fast = fast->next;
		if (fast == NULL) {
			return 0;//表示链表长度不够
		}
	}
	//判断fast指针有没有移动到空位置
	while (fast != NULL) {
		//快慢指针同步走
		fast = fast->next;
		slow = slow->next;
	}
	//循环结束表示快指针已经指向空地址 也就是最后一个节点 慢指针也就已就为倒数第pos个位置了
	printf("倒数第%d个位置元素为%d", pos, slow->data);
	return 1;
}

实现思路：

首先让快指针走N步，如果在期间快指针已经指向NULL了表示链表长度不足以找到倒数第N个位置
快指针不为NULL，表示链表长度合理，可以找到倒数N个位置
同步走，此时表示快慢指针已经间隔N个位置
当快指针指向NULL时，也就是最后一个位置，那么慢指针就已经为倒数第N个位置