discuss3

Description

已知一个带有表头结点的单链表，结点结构为（data，link），假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。

Input

多组数据，每组数据两行。第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。第三行为要查询链表的倒数索引k。

Output

输出数据一行。若查询到值则输出值，否则不输出。

Sample Input Copy

Sample Output Copy

1
5

HINT

		#include <iostream> 
	
		#define MAXSIZE 100 
	
		#define OK 1 
	
		#define ERROR 0 
	
		using namespace std; 
	
		typedef struct LNode
	
		{ 
	
		    int data; 
	
		    struct LNode *next; 
	
		}LNode,*linkList; 
	
		void CreateList_R(linkList &L,int n) 
	
		{//后插法创建单链表 
	
		    L=new LNode; 
	
		    L->next=NULL; 
	
		    linkList r=L; 
	
		    for(int i=0;i<n;i++) 
	
		    { 
	
		        linkList p=new LNode; 
	
		        cin>>p->data; 
	
		        p->next=NULL; 
	
		        r->next=p; 
	
		        r=p; 
	
		    } 
	
		} 
	
		int Search_k(linkList L,int a[],int k) 
	
		{//查找链表倒数第k个结点 
	
		//通过一趟遍历把该链表的结点都存入到一个辅助数组中，再通过数组下标可直接获取倒数第k个结点，但这样会需要额外的存储空间，因此空间复杂度为O(n) 
	
		    /**************begin************/ 
	
		    /**************end************/ 
	
		} 
	
		int main() 
	
		{ 
	
		    int n; 
	
		    while(cin>>n) 
	
		    { 
	
		        if(n==0) break; 
	
		        linkList L; 
	
		        CreateList_R(L,n); 
	
		        int k,a[MAXSIZE]; 
	
		        cin>>k; 
	
		        Search_k(L,a,k); 
	
		    } 
	
		    return 0; 
	
		}

Source/Category

数据结构课程