学步园

链表的节点结构为：

struct ListNode

{

 int data;

 ListNode * nextNode;

}

顺序查找：

int sequential_search(const List<int> &the_list,
					  const Key &target)
/*Post: If an entry in the_list is equal to target, then return the position
        of this entry. 
		Otherwise return -1 
*/
{
	int position;
	int s=the_list.size();
	for(position=0;position<s;position++){
		int data;
		the_list.retrieve(position,data);
		if(data==target){
			return position;
		}
	}
	return -1;
}

题目：输入一个单向链表，输出该链表中倒数第k个结点：

我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

实现：

#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;

typedef struct node{
        int data;
        struct node *next;
}Node,*List;

List createList(int N)
{
	List head = (List)malloc(sizeof(Node));
	head->data = 0;
	head->next=NULL;
	int count = 0;
	List p = head;
	while(count<N)
	{	count++;
		List s = (List)malloc(sizeof(Node));
		s->data = count;
		s->next = NULL;
		p->next = s;
		p = s;
	}
	return head;
}

void traverse(List head)
{
	if(head == NULL)
	{
		return;
	}
	List p = head->next;
	while(p)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}
List find(List head,int index)
{
	int count = 0;
	List first = head;
	List second = NULL;
	while(first&&count<index)//first首先找到第index个元素
	{
		first = first->next;
		count++;
	}
	//cout<<"count: "<<first->data<<endl;
	if(first!=NULL)//如果没有到链表尾
	{
		second = head;
		while(first!=NULL)
		{
			first = first->next;
			second = second->next;
		}
	}
	return second;
}
int main()
{
	int N = 20;
	List head = createList(N);
	traverse(head);
	List no = find(head,5);
	if(no!=NULL)
	{
		cout<<no->data<<endl;
	}else{
		cout<<"can't find"<<endl;
	}
    getchar();
    return 0;
}