从尾到头打印链表

题:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。链表结点定义如下:

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

//将当前的节点的p_next指向前一个节点
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》一书