【剑指offer】从尾到头打印链表

题目描述：

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表结点定义如下：

struct ListNode{

     int m_nKey;

     ListNode *m_pNext;

};

分析描述：

对于链表，如果是从头到尾的打印出链表是比较容易，但如果是从尾到头返过来打印每个结点的值就比较复杂。反序输出就是第一个遍历到的结点最后一个输出，而最后一个遍历的结点第一个输出。

这就是典型的“后进先出”，可以想到的方法一是用栈实现这种顺序。没经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值。此时输出的结点的顺序已经反转过来了。

递归在本质上就是一个栈结构，所以很自然的想到用递归来实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。但有个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈的溢出。

程序示例：

1、用栈实现的“从尾到头打印链表”程序代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#ifndef ERROR
#define ERROR (0)
#endif
#ifndef OK
#define OK	(!ERROR)
#endif

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int ElemType;
typedef struct Node{
	ElemType 	data;
	struct Node *next;
}Node, *pNode;

typedef int SElemType;
typedef struct SqStack{
	SElemType	*base;
	SElemType	*top;
	int			stacksize;
}SqStack, *pStack;
pStack 	S;

pStack InitStack(pStack S)
{
	S = (pStack)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(S == NULL){
		return ERROR;	
	}
	S->base = (SElemType *)S;
	S->top  = S->base;
	S->stacksize = STACK_INIT_SIZE;

	return S;
}

pStack Push(pStack S, SElemType e)
{
	if((S->top - S->base) >= S->stacksize){
		S->base = (SElemType *)realloc(S, 
						(S->stacksize + STACKINCREMENT) * sizeof(SElemType));	
		if(S->base == NULL)
				return ERROR;
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return S;
}

SElemType Pop(pStack S)
{
	if(S->top == S->base)
			return 0;
	return *(--S->top);
}

pNode CreateList()
{
	ElemType val;
	pNode pHead = NULL;
	pNode pCur  = NULL;

	do{
		scanf("%d", &val);
		if(val != -1){
			pNode pNew = (pNode)malloc(sizeof(Node));
			if(pNew == NULL)
				exit(EXIT_FAILURE);
			pNew->data = val;
			pNew->next = NULL;

			if(pHead == NULL){
				pHead = pNew;
				pCur  = pHead;	
			}else{
				pCur->next = pNew;
				pCur = pCur->next;	
			}
		}	
	}while(val != -1);

	return pHead;
}

void DestroyList(pNode pHead)
{
	if(pHead == NULL)
		return ;
	pNode p = NULL;
	while(pHead != NULL){
		p = pHead->next;
		free(pHead);	
		pHead = p;
	}
}

void PrintListReverse(pNode pHead)
{
	if(pHead == NULL)	
		return;
	pNode TmpNode = pHead;

	pStack S = InitStack(S);
	
	while(TmpNode != NULL){
		Push(S, TmpNode->data);	
		TmpNode = TmpNode->next;
	}

	while(S->top != S->base){
		printf("%d", Pop(S));	
	}
		
}

int
main(int argc, char **argv)
{
	pNode pHead = CreateList();
	PrintListReverse(pHead);	
	DestroyList(pHead);
	return 0;
}

2、用递归实现的“从尾到头打印链表”程序代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct Node{
	ElemType 	data;
	struct Node *next;
}Node, *pNode;

void PrintListReverse(pNode pHead)
{
	if(pHead == NULL)
		return;
	if(pHead->next != NULL)
		PrintListReverse(pHead->next);
	printf("%d\n", pHead->data);
}

pNode CreateList()
{
	ElemType val;
	pNode pHead = NULL;
	pNode pCur  = NULL;

	do{
		scanf("%d", &val);
		if(val != -1){
			pNode pNew = (pNode)malloc(sizeof(Node));
			if(pNew == NULL)
				exit(EXIT_FAILURE);
			pNew->data = val;
			pNew->next = NULL;

			if(pHead == NULL){
				pHead = pNew;
				pCur  = pHead;	
			}else{
				pCur->next = pNew;
				pCur = pCur->next;	
			}
		}	
	}while(val != -1);

	return pHead;
}

void DestroyList(pNode pHead)
{
	if(pHead == NULL)
		return ;
	pNode p = NULL;
	while(pHead != NULL){
		p = pHead->next;
		free(pHead);	
		pHead = p;
	}
}

int
main(int argc, char **argv)
{
	pNode pHead = CreateList();
	PrintListReverse(pHead);	
	DestroyList(pHead);
	return 0;
}

1、对于反向输出时，应该考虑它的特性，选择数据结构类型进行实现。一定要搞清楚各种数据结构类型的特点。

2、对于栈能实现的例子，一般要想到也可以用递归来完成。递归的缺点就是递归层级很深时，可能导致函数调用栈溢出。

注意上面的第一个程序有点小小的bug，另外本篇参考：http://blog.csdn.net/ns_code/article/details/25028525

【剑指offer】从尾到头打印链表,布布扣,bubuko.com

【剑指offer】从尾到头打印链表

原文：http://blog.csdn.net/to_be_it_1/article/details/36023067