从尾到头打印链表
题：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表结点定义如下：
1
2
3
4
5
| struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
|
思路：
我们首先想到的是链表的翻转，这也是我们的第一思路。但链表的翻转会改变原来链表的结构，如果不允许在打印链表的时候修改链表的结构呢？
分析：打印链表首先需要遍历链表，遍历的顺序是从头到尾，但要求的输出顺序是：从尾到头。这种方式为典型的”后进先出”，所以可以用栈实现这种顺序。每遍历一个节点，就将该节点放入栈中。当遍历完整个链表后，再从栈顶开始逐个输出节点的值。这样得到的顺序就是从尾到头的顺序。
所以完成该题有两种思路：
1、在没有要求不允许更改链表结构的情况下，利用链表的翻转可以完成该题。
2、分析该题的要求，根据符合栈的”后进先出”这一特性，利用栈来完成该题。
代码实践：
1、链表翻转
1.1循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| ListNode* revereList(ListNode* pHead){
ListNode* pNode = pHead;
ListNode* pPrev = nullptr;
ListNode* pNext = nullptr;
ListNode* pReverseHead = nullptr;
while (pNode != nullptr) {
pNext = pNode->p_next;
if (pNext == NULL) {
pReverseHead = pNode;
}
pNode->p_next = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pReverseHead;
}
int main()
{
ListNode *head=new ListNode(1);
ListNode *p1=new ListNode(2);
ListNode *p2=new ListNode(3);
head->p_next=p1;
p1->p_next=p2;
ListNode *p=revereList(head);
while(p)
{
cout<<p->val<<endl;
p = p->p_next;
}
return 0;
}
|
1.2递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| ListNode* revereList(ListNode* pHead, ListNode* &newHead){
if (pHead == NULL) {
return NULL;
}
ListNode* nextHead = pHead->p_next;
if (nextHead == NULL) {
newHead = pHead;
}else {
revereList(nextHead, newHead);
nextHead->p_next = pHead;
pHead->p_next = NULL;
}
return newHead;
}
int main()
{
ListNode *head=new ListNode(1);
ListNode *p1=new ListNode(2);
ListNode *p2=new ListNode(3);
head->p_next=p1;
p1->p_next=p2;
ListNode *newhead=NULL;
ListNode *p=revereList(head,newhead);
while(p)
{
cout<<p->val<<endl;
p = p->p_next;
}
return 0;
}
|
2、利用栈的”后进先出”实现
1.1 循环实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void printListNodeReverse_Iteratively(ListNode* pHead)
{
std::stack<ListNode*>nodes;
ListNode* pNode = pHead;
while (pNode != NULL) {
nodes.push(pNode);
pNode = pNode->p_next;
}
while (!nodes.empty()) {
pNode = nodes.top();
printf("%d\t",pNode->val);
nodes.pop()
}
}
|
1.2递归实现
由于递归本质就是一个栈结构，所以可以直接用递归实现，要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点自己，这样链表的输出结果就反过来了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void printListNodeReverse_Iteratively(ListNode* pHead)
{
if (pHead != NULL) {
if (pHead ->p_next != NULL) {
printListNodeReverse_Iteratively(pHead ->p_next);
}
printf("%d\t",pHead->p_value);
}
}
int main()
{
ListNode *head=new ListNode(1);
ListNode *p1=new ListNode(2);
ListNode *p2=new ListNode(3);
head->p_next=p1;
p1->p_next=p2;
printListNodeReverse_Iteratively(head);
return 0;
}
|
注：本篇所有思路均参考或直接引用《剑指offer》一书
