【数据结构与算法】查找带头结点的单链表中倒数第k个结点的算法 C++实现（单链表+双指针法）

设L是一个带头结点的单链表的表头指针,结点结构为(data，Link)，在不改变链表的前提下，设计一个算法，查找链表中倒数第k个结点（k为正整数）。若查找成功，算法输出该结点的元素值，并返回1；否则，只返回0。

思路

双指针法，同时使用两个指针p1和p2。两个指针都指向链表的头节点。然后，指针p1开始遍历链表，每次前进一步。当p1前进到第k+1个节点时，指针p2开始从头节点开始遍历。这样，p1和p2始终保持k个节点的距离。当p1到达链表的末尾时，p2刚好位于链表的倒数第k个节点。

声明两个指针p1和p2，并将它们都初始化为指向链表的头节点。然后，使用一个for循环遍历链表。在每次迭代中，p1都向前移动一步。当p1移动了k步后，p2开始移动。

如果链表的长度小于k，那么p1将在p2开始移动之前到达链表的末尾。在这种情况下，函数返回ERROR，表示无法找到倒数第k个元素。

如果链表的长度大于或等于k，那么当p1到达链表的末尾时，p2将指向链表的倒数第k个元素。然后，函数打印p2指向的节点的数据，并返回OK，表示成功找到了倒数第k个元素。

由于每个节点只被访问一次，因此时间复杂度为$O(n)$，其中$n$是链表的长度。这个算法只使用了常量级别的额外空间（两个指针p1和p2），所以空间复杂度为$O(1)$。

代码

#include <algorithm> #include <iostream> #define AUTHOR "HEX9CF" using namespace std; using Status = int; using ElemType = int;  const int N = 1e6 + 7; const int TRUE = 1; const int FALSE = 0; const int OK = 1; const int ERROR = 0; const int INFEASIBLE = -1; const int OVERFLOW = -2;  int n; ElemType a[N];  struct ListNode { 	ElemType data; 	ListNode *next; }; using LinkedList = ListNode *;  Status initList(LinkedList &first) { 	first = (ListNode *)malloc(sizeof(ListNode)); 	first->next = NULL; 	return OK; }  Status listInsert(LinkedList &L, int pos, ElemType e) { 	ListNode *p = L; 	for (int i = 0; p && i < pos; i++) { 		p = p->next; 	} 	if (!p) { 		return ERROR; 	} 	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); 	newNode->data = e; 	newNode->next = p->next; 	p->next = newNode; 	return OK; }  ElemType getElem(LinkedList L, int pos) { 	ListNode *p = L->next; 	for (int i = 0; p && i < pos; i++) { 		p = p->next; 	} 	return p->data; }  ElemType getNthLastElem(LinkedList L, int k) { 	int i; 	ListNode *p1, *p2; 	p1 = p2 = L->next; 	for (i = 0; p1; i++) { 		p1 = p1->next; 		if (i > k) { 			p2 = p2->next; 		} 	} 	if (i < k) { 		return ERROR; 	} 	cout << p2->data << "\n"; 	return OK; }  int main() { 	cin >> n; 	for (int i = 0; i < n; i++) { 		cin >> a[i]; 	}  	int k; 	cin >> k;  	LinkedList L; 	initList(L);  	for (int i = 0; i < n; i++) { 		listInsert(L, i, a[i]); 	}  	// for (int i = 0; i < n; i++) { 	// 	cout << getElem(L, i) << " "; 	// } 	// cout << "\n";  	cout << getNthLastElem(L, k) << "\n"; 	return 0; }