您的当前位置：首页 CrackingtheCodingInterviewQ2.2

CrackingtheCodingInterviewQ2.2

来源：好走旅游网

题干如下： /* Instruction: Implement an algorithm to find the kth to last element of a singly linked list. */ 我用了一个private一个public函数实现。 public函数是由main函数调用，然后public的函数又调用private，这主要是因为传递函数包括头指针

题干如下：

/* Instruction: Implement an algorithm to find the kth to last element of a singly linked list. */

我用了一个private+一个public函数实现。

public函数是由main函数调用，然后public的函数又调用private，这主要是因为传递函数包括头指针，而头指针在我写的类里面是一个private类型。

public函数如下所示：

/* find the kth to last element */
node* linkedlist::kth(int k) {
	int i = 0;
	node* result = kth(head, k, i);
//	cout << result->character << endl;
	return result;
}

很直观，不需要解释，就是调用一个private函数，如下所示：

node* linkedlist::kth(node* head, int k, int& i) {
	if(head == NULL)
	return NULL;
	node* current = kth(head->next, k, i);
	++i;
	if (i == k) {
	cout << head->character << endl;
	return head;
	}
	return current;
}

运用recursive，不断地将current指针向后移，指向尾指针，当执行kth(tail, k, i)时，i=0，之后每执行完一个函数，则++i。当i = k时，就可以得到倒数第k个node指向的È。

另外补充一定，之所以用int& i是因为i的È要不断更新，所以每个function的i的地址都要一样，故用了引用标志&

源码如下： https://github.com/YimengL/CTCI-cpp/blob/master/2_2.cpp