C语言数据结构——链表应用（双指针）

题目

已知一个带有表头节点的单链表，节点结构为：

data	next

假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。

若查找成功，算法输出该节点 data 域的值，并返回 1；否则，只返回 0。

要求

1. 描述算法的基本思想；
2. 描述算法的详细实现步骤；
3. 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处给出简要注释。

思考

循环遍历两次链表确实可行：

1. 第一次得到链表长度 length；
2. 第二次计算并定位倒数第 k 个结点。

但这样不够简洁高效，因此采用双指针（快慢指针）方法。

首先，建立两个指针（fast，slow）同时指向链表的head或者head的next。(我们假设k=2)

然后让指针fast先移动k次(假设k=2)。

再让fast和slow指针同步移动，我们会发现，当fast指针指向NULL的时候，slow指针指向的就是要查找的数据。

参考函数代码（无注释）

int findNode(Node *L,int k)
{
	Node *slow = L->next;
	Node *fast = L->next;
	for (int i = 0;i < k;i++)
	{
		if(fast == NULL)
		{
			printf("not found");
			return 0;
		}
		fast = fast->next;
	}
	while(fast != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}
	printf("data=%d",slow->data);
	return 1;
}

完整测试代码（无注释）

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef int ElemType;

typedef struct node{
	ElemType data;
	struct node *next;
}Node;

Node* initNode()
{
	Node *head = (Node*)malloc(sizeof(Node));
	head->data = 0;
	head->next = NULL;
	return head;
}

Node* getTail(Node *L)
{
	Node *p = L;
	while(p->next != NULL)
	{
		p = p->next;
	}
	return p;
}

Node* insertTail(Node *tail,ElemType e)
{
	Node *p = (Node*)malloc(sizeof(Node));
	p->data = e;
	p->next = NULL;
	tail->next = p;
	return p;
}

int listNode(Node *L)
{
	Node *p = L->next;
	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return 1;
}

int findNode(Node *L,int k)
{
	Node *slow = L->next;
	Node *fast = L->next;
	for (int i = 0;i < k;i++)
	{
		if(fast == NULL)
		{
			printf("not found");
			return 0;
		}
		fast = fast->next;
	}
	while(fast != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}
	printf("data=%d",slow->data);
	return 1;
}

int main()
{
	Node *list = initNode();
	Node *tail = getTail(list);
	tail = insertTail(tail,10);
	tail = insertTail(tail,20);
	tail = insertTail(tail,30);
	tail = insertTail(tail,40);
	tail = insertTail(tail,50);
	tail = insertTail(tail,60);
	tail = insertTail(tail,70);
	tail = insertTail(tail,80);
	listNode(list);
	int n;
	scanf("%d",&n);
	findNode(list,n);
	return 0;
}