Cracking the coding interview--Q2.2

December 14, 2012
作者:Hawstein
出处:http://hawstein.com/posts/2.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Implement an algorithm to find the nth to last element of a singly linked list.

译文:

实现一个算法从一个单链表中返回倒数第n个元素。

解答

这道题的考点在于我们怎么在一个单链表中找到倒数第n个元素? 由于是单链表,所以我们没办法从最后一个元素数起,然后数n个得到答案。 但这种最直观的思路显然是没错的,那我们有没有办法通过别的方式,从最后的元素数起数 n个来得到我们想要的答案呢。

这个次序颠倒的思路可以让我们联想到一种数据结构:栈。

我们如果遍历一遍单链表,将其中的元素压栈,然后再将元素一一出栈。那么, 第n个出栈的元素就是我们想要的。

那我们是不是需要显式地用栈这么一个结构来做这个问题呢?答案是否。看到栈,我们应当 要想到递归,它是一种天然使用栈的方式。所以,第一种解决方案用递归,让栈自己帮我 们从链表的最后一个元素数起。

思路很简单,如果指向链表的指针还未空,就不断递归。当指针为空时开始退递归,这个过 程n不断减1,直接等于1,即可把栈中当前的元素取出。代码如下:

node *pp;
int nn;
void findNthToLast1(node *head){
    if(head==NULL) return;
    findNthToLast1(head->next);
    if(nn==1) pp = head;
    --nn;
}

递归的特点就是理解直接,代码短小。所以,很多递归代码看起来都很漂亮(不包括我这个 哈,还用了两个全局变量,比较不美观)。除了递归,这道题目还有别的方法还做吗? 答案还是有。虽然我们没办法从单链表的最后一个元素往前数,但如果我们维护两个指针, 它们之间的距离为n。然后,我将这两个指针同步地在这个单链表上移动,保持它们的距离 为n不变。那么,当第二个指针指到空时,第一个指针即为所求。很tricky的方法, 将这个问题很漂亮地解决了。代码如下:

node* findNthToLast(node *head, int n){
    if(head==NULL || n < 1) return NULL;
    node *p=head, *q=head;
    while(n>0 && q){
        q = q->next;
        --n;
    }
    if(n > 0) return NULL;
    while(q){
        p = p->next;
        q = q->next;
    }
    return p;
}

没有额外的全局变量,代码看起来就要漂亮一些。:P

完整代码如下:

#include < iostream >
using namespace std;

typedef struct node{
	int data;
	node *next;
}node;

node* init(int a[], int n){
	node *head, *p;
	for(int i=0; i < n; ++i){
	node *nd = new node();
	nd->data = a[i];
	if(i==0){
		head = p = nd;
		continue;
	}
	p->next = nd;
	p = nd;
	}
	return head;
}

node* findNthToLast(node *head, int n){
	if(head==NULL || n < 1) return NULL;
	node *p=head, *q=head;
	while(n > 0 && q){
	q = q->next;
	--n;
	}
	if(n > 0) return NULL;
	while(q){
	p = p->next;
	q = q->next;
	}
	return p;
}
node *pp;
int nn;
void findNthToLast1(node *head){
	if(head==NULL) return;
	findNthToLast1(head->next);
	if(nn==1) pp = head;
	--nn;
}
int main(){
	int n = 10;
	int a[] = {
	9, 2, 1, 3, 5, 6, 2, 6, 3, 1 
	};
	node *head = init(a, n);
	node *p = findNthToLast(head, 6);
	if(p) cout<<p->data<<endl;
	else cout << "the length of link is not long enough" << endl;
	nn = 6;
	findNthToLast1(head);
	if(pp) cout << pp->data << endl;
	return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview