# 剑指Offer - 面试题6：从尾到头打印链表

### 题目

struct ListNode
{
int m_nKey;
struct ListNode* m_pNext;
};

### 思路

C

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct ListNode
{
int m_nKey;
struct ListNode* m_pNext;
};
/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(struct ListNode** L, int n)
{
struct ListNode* p;
struct ListNode* r;
int i;
srand((unsigned int)time(NULL));                        /* 初始化随机数种子 */
*L = (struct ListNode*)malloc(sizeof(struct ListNode)); /* L为整个线性表 */
r = *L;                                      /* r为指向尾部的结点 */
for (i = 0; i < n; i++)
{
p = (struct LilstNode*)malloc(sizeof(struct ListNode)); /*  生成新结点 */
if (NULL == (*L))
{
perror("开辟子节点空间失败");
}
p->m_nKey = rand() % 10;                   /*  随机生成100以内的数字 */
r->m_pNext = p;                          /* 将表尾终端结点的指针指向新结点 */
r = p;                                   /* 将当前的新结点定义为表尾终端结点 */
}
r->m_pNext = NULL;                           /* 表示当前链表结束 */
}
/* 初始条件：链式线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
void ListTraverse(struct ListNode* L)
{
struct ListNode* p = L->m_pNext;
while (p != NULL)
{
printf("%d ", p->m_nKey);
p = p->m_pNext;
}
printf("\n");
}
void PrintListReversing(struct ListNode* L)
{
int* n = (int*)malloc(10 * sizeof(int));
int size = 0;           //实际元素个数
int length = 10;        //数组长度
struct ListNode* p = L->m_pNext;
while (p != NULL)
{
if (size + 1 == length)//扩容
{
length += 10;
int* tmp = (int*)realloc(n, length * sizeof(int));
if (NULL == tmp)
{
perror("扩充失败！");
}
n = tmp;
tmp = NULL;
}
n[size++] = p->m_nKey;
p = p->m_pNext;
}
for (int i = size - 1; i >= 0; i--)
{
printf("%d ", n[i]);
}
}
int main()
{
struct ListNode* L;
CreateListTail(&L, 10);
printf("从前到后打印\n");
ListTraverse(L);
printf("从尾到头打印\n");
PrintListReversing(L);
return 0;
}

C++

#include <string>
#include <iostream>
#include <stack>
using namespace std;
class Node
{
public:
int data;
Node* next;
};
{
public:
int size;
};
{
size = 0;
}
{
}
{
if (n < 0) {
printf("error\n");
return -1;
}
Node* ptemp = NULL;
Node* pnew = NULL;
this->size = n;
for (int i = 0; i < n; i++)
{
pnew = new Node;
pnew->next = NULL;
cout << "输入第" << i + 1 << "个节点值" << endl;
cin >> pnew->data;
ptemp->next = pnew;
ptemp = pnew;
}
cout << "创建完成" << endl;
return 0;
}
{
Node* ptemp = NULL;
cout << "链表原本就为空" << endl;
return -1;
}
{
}
cout << "销毁链表完成" << endl;
return 0;
}
{
cout << "链表为空" << endl;
return -1;
}
while (ptemp)
{
cout << ptemp->data << "->";
ptemp = ptemp->next;
}
cout << "NULL" << endl;
return 0;
}
void PrintListReversing(Node* list)//从尾到头打印
{
stack<int> nodes;
Node* ptemp = list->next;
while (ptemp != NULL)
{
nodes.push(ptemp->data);
ptemp = ptemp->next;
}
int temp = 0;
cout << "从尾到头打印链表" << endl;
while (nodes.empty() == false)//不为空
{
temp = nodes.top();
cout << temp << " ";
nodes.pop();
}
cout << endl;
}
int main(void)
{
system("pause");
return 0;
}

C++

#include <string>
#include <iostream>
#include <stack>
using namespace std;
class Node
{
public:
int data;
Node* next;
};
{
public:
int size;
};
{
size = 0;
}
{
}
{
if (n < 0) {
printf("error\n");
return -1;
}
Node* ptemp = NULL;
Node* pnew = NULL;
this->size = n;
for (int i = 0; i < n; i++)
{
pnew = new Node;
pnew->next = NULL;
cout << "输入第" << i + 1 << "个节点值" << endl;
cin >> pnew->data;
ptemp->next = pnew;
ptemp = pnew;
}
cout << "创建完成" << endl;
return 0;
}
{
Node* ptemp = NULL;
cout << "链表原本就为空" << endl;
return -1;
}
{
}
cout << "销毁链表完成" << endl;
return 0;
}
{
cout << "链表为空" << endl;
return -1;
}
while (ptemp)
{
cout << ptemp->data << "->";
ptemp = ptemp->next;
}
cout << "NULL" << endl;
return 0;
}
void PrintListReversing(Node* list)//从尾到头打印
{
if (NULL != list)
{
if (list->next != NULL)
{
PrintListReversing(list->next);
}
cout << list->data << " ";
}
}
int main(void)
{
system("pause");
return 0;
}

|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
38 5
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案，通过使用双指针法找到并删除链表中值为特定数值的节点，然后返回更新后的链表头节点。
30 4
|
18天前
|

【面试题】合井K个升序链表
【面试题】合井K个升序链表
22 0
|
18天前
|

【Java集合类面试十】、HashMap中的循环链表是如何产生的？

12 0
|
4月前
|

36 0
|
3月前
|

LeetCode 83题：删除排序链表中的重复元素【面试】
LeetCode 83题：删除排序链表中的重复元素【面试】
19 0
|
4月前
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
34 0
|
18天前
|

【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输，之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
28 2
|
18天前
|
XML 存储 JSON
【IO面试题 六】、 除了Java自带的序列化之外，你还了解哪些序列化工具？

30 2
|
18天前
|
Java
【Java基础面试三十七】、说一说Java的异常机制

14 2