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

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

#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;
}

#include <string>
#include <iostream>
#include <stack>
using namespace std;
class Node
{
public:
  int data;
  Node* next;
};
class LinkList
{
public:
  LinkList();
  ~LinkList();
  int CreateLinkList(int size);
  int BYELinkList();
  int TravalLinkList();
  Node* head;
  int size;
};
LinkList::LinkList()
{
  head = new Node;
  head->data = 0;
  head->next = NULL;
  size = 0;
}
LinkList::~LinkList()
{
  delete head;
}
int LinkList::CreateLinkList(int n)//创建链表
{
  if (n < 0) {
    printf("error\n");
    return -1;
  }
  Node* ptemp = NULL;
  Node* pnew = NULL;
  this->size = n;
  ptemp = this->head;
  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;
}
int LinkList::BYELinkList()//销毁链表
{
  Node* ptemp = NULL;
  if (this->head == NULL) {
    cout << "链表原本就为空" << endl;
    return -1;
  }
  while (this->head)
  {
    ptemp = head->next;
    delete head;
    head = ptemp;
  }
  cout << "销毁链表完成" << endl;
  return 0;
}
int LinkList::TravalLinkList()//输出链表
{
  Node* ptemp = this->head->next;
  if (this->head == NULL) {
    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)
{
  LinkList list;
  LinkList* plist = &list;
  plist->CreateLinkList(5);
  plist->TravalLinkList();
  PrintListReversing(plist->head);
  plist->BYELinkList();
  system("pause");
  return 0;
}