剑指offer之反向打印链表值

1 问题

反向打印链表值

2 思考

1） 我们利用栈的思想，新进后出，把链表的每个元素分别入栈之后再打印栈

2）既然上面用到了栈，我们应该就会想到用到递归来实现

3 代码实现

#include <iostream>
#include <stack>
#include <stdlib.h>

using namespace std;

typedef struct node
{
int value;
struct node *next;
} Node;

/**
 *把链表的每一个元素遍历出来放进栈,然后利用
 *栈把先进后出的特点,然后打印栈
 */
void reverse_printf(Node *head)
{
if (head == NULL)
{
std::cout << "head is NULL" << std::endl;
return;
}
Node *p = head;
stack<Node *> stk;
while (p != NULL)
{
stk.push(p);
p = p->next;
}
while(!stk.empty())
{
Node *node = stk.top();
std::cout << node->value << std::endl;
stk.pop();
}
}

/**
 *既然上面用到了栈,那么我们自然而然就会想到
 *用递归的思想,我们就自己调用自己直到遍历到最后
 *很明显我们递归的条件是最后一个原始的next不能为空
 */
void reverse_printf1(Node *head)
{
/**这样也行
if (head == NULL)
{
return;
}
reverse_printf1(head->next);
std::cout << head->value << std::endl;**/
if (head != NULL)
{
reverse_printf1(head->next);
std::cout << head->value << std::endl;
}
}

void printf(Node *head)
{
if (head == NULL)
{
std::cout << "head is NULL" << std::endl;
return;
}
Node *p = head;
while (p != NULL)
{
std::cout << p->value << std::endl;
p = p->next;
}
}

int main()
{
Node *head = NULL;
Node *node1 = NULL;
Node *node2 = NULL;
Node *node3 = NULL;
head = (struct node*)malloc(sizeof(Node));
node1 = (struct node*)malloc(sizeof(Node));
node2 = (struct node*)malloc(sizeof(Node));
node3 = (struct node*)malloc(sizeof(Node));
if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL)
{
std::cout << "malloc fail" << std::endl;
return -1;
}
head->value = 0;
head->next = node1;

node1->value = 1;
node1->next = node2;

node2->value = 2;
node2->next = node3;

node3->value = 3;
node3->next = NULL;

printf(head);
std::cout << "***************" << std::endl;
reverse_printf(head);
std::cout << "***************" << std::endl;
reverse_printf1(head);
free(head);
free(node1);
free(node2);
free(node3);
return 0;

}

4 运行结果

0
1
2
3
***************
3
2
1
0
***************
3
2
1
0