打印列表从尾部到头部

全栈程序员站长

发布于 2022-07-06 12:05:12

53600

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

大家好，又见面了，我是全栈君

题目描写叙述：

输入一个链表，从尾到头打印链表每一个节点的值。

输入：

每一个输入文件仅包括一组測试例子。

每一组測试案例包括多行，每行一个大于0的整数，代表一个链表的节点。第一行是链表第一个节点的值，依次类推。

当输入到-1时代表链表输入完成。-1本身不属于链表。

输出：

相应每一个測试案例，以从尾到头的顺序输出链表每一个节点的值。每一个值占一行。

例子输入：

12345-1

例子输出：

解法一：

1.遍历链表，使用栈结构来存储链表元素。

2.链表出栈即从尾到头打印链表。

代码：

/********************************************从尾到头打印链表by Rowandjj2014/7/18********************************************/#include<iostream>#include<stdlib.h>using namespace std;typedef struct _NODE_//单链表结点定义{	int data;	struct _NODE_ *next;}Node,*pNode;typedef struct _STACK_//栈结构{	pNode head;	int size;}Stack,*pStack;void InitStack(pStack stack){	pNode pNew = (Node*)malloc(sizeof(Node));	if(!pNew)	{		return;	}	pNew->next = NULL;	stack->head = pNew;	stack->size = 0;}void Push(pStack stack,int data){	pNode pNew = (Node*)malloc(sizeof(Node));	if(!pNew)	{		return;	}	pNew->data = data;	pNew->next = stack->head->next;	stack->head->next = pNew;	stack->size++;}int pop(pStack stack){	if(stack->size == 0)	{		return -1;	}	pNode pDel = stack->head->next;	stack->head->next = pDel->next;	int data = pDel->data;	free(pDel);	return data;}void ReversePrint(pNode phead){	Stack s;	InitStack(&s);	if(phead == NULL)	{		return;	}	pNode p = phead;	while(p != NULL)	{		Push(&s,p->data);		p = p->next;	}	int num = s.size;	for(int i =0; i < num; i++)	{		printf("%d\n",pop(&s));	}}int main(){	int data;	scanf("%d",&data);	if(data == -1)	{		exit(-1);	}	pNode pHead = (Node*)malloc(sizeof(Node));	if(!pHead)	{		exit(-1);	}	pHead->data = data;	pHead->next = NULL;	pNode p = pHead;	while(scanf("%d",&data))	{		if(data == -1)		{			break;		}		pNode pTemp = (Node*)malloc(sizeof(Node));		if(!pTemp)		{			exit(-1);		}		pTemp->data = data;		pTemp->next = NULL;		p->next = pTemp;		p = pTemp;	}	ReversePrint(pHead);	return 0;}

解法2：

递归就是简单啊。！

#include<stdlib.h>
#include<stdio.h>
typedef struct _NODE_
{
	int data;
	struct _NODE_ *next;
}Node,*pNode;
//递归 从后往前遍历链表
void Reverse(pNode pHead)
{
	if(pHead == NULL)
	{
		return;
	}
	if(pHead->next != NULL)
	{
		Reverse(pHead->next);
	}
	printf("%d\n",pHead->data);
}
int main()
{
	pNode pHead;
	int data;
	scanf("%d",&data);
	if(data == -1)
	{
		exit(-1);
	}
	pHead = (pNode)malloc(sizeof(Node));
	if(!pHead)
	{
		exit(-1);
	}
	pHead->data = data;
	pHead->next = NULL;
	pNode p = pHead;
	while(scanf("%d",&data) != -1)
	{
		if(data == -1)
		{
			break;
		}
		pNode pNew = (pNode)malloc(sizeof(Node));
		if(!pNew)
		{
			exit(-1);
		}
		pNew->data = data;
		pNew->next = NULL;
		p->next = pNew;
		p = pNew;
	}
	Reverse(pHead);
	//销毁
	pNode pt = pHead,q;
	while(pt)
	{
		q = pt->next;
		free(pt);
		pt = q;
	}
	return 0;
}