查找单链表倒数第 k 个元素

查找单链表倒数第 m 个结点，要求时间复杂度为 O(n).(提示，使用双指针)

解题思路：
常规思路为先获取链表的长度 N，然后返回 N-k+1 位置处的结点即可。但是中需要遍历两次链表。
我们使用另一种算法，设定两个指针 p1,p2.将这两个指针都向第一个结点，让 p1 先走 k 步，然后两个指针一起向后移动，当 p1 到达最后一个结点时，p2 指针刚好指向链表的倒数第 k 个结点。

关键算法：

int getK(Node *link, int k)
{
  Node *p1, *p2;
  int i;
  if (link->next == NULL || k == 0)
	return -1;
  p1 = link->next;
  for (i = 1; i < k; i++) 
  { 
	if (p1->next == NULL)
	  return -1;
	p1 = p1->next;
  }
  p2 = link->next;
  while (p1->next != NULL)
  {
	p1 = p1->next;
	p2 = p2->next;
  }
  return p2->number;
}

完整程序如下：

/**************************************************************
Problem: 查找单链表倒数第N个元素，要求复杂度O(n)
User: xiaoming
Language: C
****************************************************************/

#include
#include

typedef struct node
{
  int number;
  struct node * next;
} Node;

int getK(Node *link, int k);

int main()
{
  int n, k, i, temp;
  int flag;
  while (scanf("%d %d", &n, &k) != EOF && n >= 0 && n <= 1000 && k >= 0 && k <= 1000) 
  { 
	Node *link = (Node *)malloc(sizeof(Node)); 
	link->next = NULL;
	flag = 0;
	Node *tail;
	tail = link;
	for (i = 0; i < n; i++) 
	{ 
	  //scanf("%d", &temp); 
	  Node *n = (Node *)malloc(sizeof(Node)); 
	  n->next = tail->next;
	  tail->next = n;
	  tail = tail->next;
	  n->number = i + 1;
	}
	int numberK = getK(link, k);
	numberK == -1 ? printf("NULL\n") : printf("%d\n", numberK);
  }
  return 0;
}
int getK(Node *link, int k)
{
  Node *p1, *p2;
  int i;
  if (link->next == NULL || k == 0)
  return -1;
  p1 = link->next;
  for (i = 1; i < k; i++) 
  { 
	if (p1->next == NULL)
	  return -1;
	p1 = p1->next;
  }
  p2 = link->next;
  while (p1->next != NULL)
  {
	p1 = p1->next;
	p2 = p2->next;
  }
  return p2->number;
}