（说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”）
题目
输入一个链表的头结点， 从尾到头反过来打印出每个结点的值。
进一步详细说明：
不允许在打印时修改链表的结构。链表结点可定义为：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
算法设计思想
正常情况，遍历链表都是从前到后的，即从头到尾。如果从尾到头打印链表元素，可以借助栈的 “后入先出” （Last in, First out）的性质，在正向遍历时将链表元素依次压栈，当到达链表末尾时，再依次弹出并打印。
具体实现可以采用两种方法：迭代和递归。正如书中所说，“递归在本质上就是一个栈结构”。递归实现，从理论上，完全可以利用栈结构转换为非递归实现，即迭代方法。
C++ 实现
#include <iostream>
#include <stack>
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void AddToTail(ListNode** pHead, int value)
{
ListNode* pNew = new ListNode();
pNew->m_nKey = value;
pNew->m_pNext = NULL;
if (*pHead == NULL)
{
*pHead = pNew;
}
else
{
ListNode* pNode = *pHead;
while (pNode->m_pNext != NULL)
pNode = pNode->m_pNext;
pNode->m_pNext = pNew;
}
}
void PrintLinkedList(const ListNode* head)
{
if (head == NULL) // 易漏点
return;
ListNode* ptr = (ListNode*) head;
while (ptr->m_pNext != NULL)
{
std::cout << ptr->m_nKey << " -> ";
ptr = ptr->m_pNext;
}
std::cout << ptr->m_nKey << std::endl;
}
void DestroyLinkedList(ListNode** pHead)
{
if (pHead == NULL || *pHead == NULL) // 易漏点
return;
ListNode* pNode = NULL;
while (*pHead != NULL)
{
pNode = *pHead;
*pHead = (*pHead)->m_pNext;
delete pNode;
}
}
// Iterative method
void PrintListReversingly_Iteratively(const ListNode* pHead)
{
if (pHead == NULL)
return;
ListNode* pNode = (ListNode*) pHead;
std::stack<ListNode*> nodes;
while (pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while (!nodes.empty())
{
pNode = nodes.top();
nodes.pop();
std::cout << pNode->m_nKey << ", ";
}
std::cout << std::endl;
}
// Recursive method
void PrintListReversingly_Recursively(const ListNode* pHead)
{
if (pHead != NULL)
{
if (pHead->m_pNext != NULL)
{
PrintListReversingly_Recursively(pHead->m_pNext);
}
std::cout << pHead->m_nKey << ", ";
}
}
void unitest()
{
ListNode* head = NULL;
AddToTail(&head, 1);
AddToTail(&head, 2);
AddToTail(&head, 3);
AddToTail(&head, 5);
AddToTail(&head, 4);
std::cout << "Print forward: ";
PrintLinkedList(head);
std::cout << "Print reversely iteratively: ";
PrintListReversingly_Iteratively(head);
std::cout << "Print reversely recursively: ";
PrintListReversingly_Recursively(head);
// Release memory
DestroyLinkedList(&head); // 易漏点
}
int main()
{
unitest();
return 0;
}
Python 实现
#!/usr/bin/python
# -*- coding: utf8 -*-
from __future__ import print_function
class ListNode:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def add_to_tail(head, value):
q = ListNode(value)
if head is None:
head = q
else:
p = head
while p.next is not None:
p = p.next
p.next = q
return head
def print_list_reversely_iteratively(head):
p = head
stack = []
# Push into stack
while p is not None:
stack.append(p.value)
p = p.next
# Pop from stack
while stack:
elem = stack.pop()
print(elem, end=', ')
print('')
def print_list_reversely_recursively(head):
if head is None:
return
if head.next is not None:
print_list_reversely_recursively(head.next)
print(head.value, end=', ')
def print_linked_list_forward(head):
if head is None:
print("This linked list is empty!")
return
p = head
while p is not None:
print(p.value, end='')
if p.next is not None:
print(' -> ', end='')
p = p.next
print('')
def unitest():
linked_list = None
linked_list = add_to_tail(linked_list, 1)
linked_list = add_to_tail(linked_list, 2)
linked_list = add_to_tail(linked_list, 3)
linked_list = add_to_tail(linked_list, 5)
linked_list = add_to_tail(linked_list, 4)
print("Print forward: ", end='')
print_linked_list_forward(linked_list)
print("Print reversely iteratively: ", end='')
print_list_reversely_iteratively(linked_list)
print("Print reversely recursively: ", end='')
print_list_reversely_recursively(linked_list)
if __name__ == '__main__':
unitest()
注：使用 Python 利用函数建立链表时，需要注意函数参数的值传递和引用传递，此为易错点。
参考代码
1. targetver.h (05_PrintListInReversedOrder/ 目录)
#pragma once
// The following macros define the minimum required platform. The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run
// your application. The macros work by enabling all features available on platform versions up to and
// including the version specified.
// Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
2. stdafx.h (05_PrintListInReversedOrder/ 目录)
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
// TODO: reference additional headers your program requires here
3. stdafx.cpp (05_PrintListInReversedOrder/ 目录)
// stdafx.cpp : source file that includes just the standard includes
// PrintListInReversedOrder.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information
#include "stdafx.h"
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
4. PrintListInReversedOrder.cpp
// PrintListInReversedOrder.cpp : Defines the entry point for the console application.
//
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛
#include "stdafx.h"
#include "..UtilitiesList.h"
#include <stack>
void PrintListReversingly_Iteratively(ListNode* pHead)
{
std::stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while(!nodes.empty())
{
pNode = nodes.top();
printf("%d ", pNode->m_nValue);
nodes.pop();
}
}
void PrintListReversingly_Recursively(ListNode* pHead)
{
if(pHead != NULL)
{
if (pHead->m_pNext != NULL)
{
PrintListReversingly_Recursively(pHead->m_pNext);
}
printf("%d ", pHead->m_nValue);
}
}
void Test(ListNode* pHead)
{
PrintList(pHead);
PrintListReversingly_Iteratively(pHead);
printf("
");
PrintListReversingly_Recursively(pHead);
}
// 1->2->3->4->5
void Test1()
{
printf("
Test1 begins.
");
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
Test(pNode1);
DestroyList(pNode1);
}
// 只有一个结点的链表: 1
void Test2()
{
printf("
Test2 begins.
");
ListNode* pNode1 = CreateListNode(1);
Test(pNode1);
DestroyList(pNode1);
}
// 空链表
void Test3()
{
printf("
Test3 begins.
");
Test(NULL);
}
int _tmain(int argc, _TCHAR* argv[])
{
Test1();
Test2();
Test3();
return 0;
}
5. targetver.h (Utilities/ 目录)
#pragma once
// The following macros define the minimum required platform. The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run
// your application. The macros work by enabling all features available on platform versions up to and
// including the version specified.
// Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef WINVER // Specifies that the minimum required platform is Windows Vista.
#define WINVER 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
#ifndef _WIN32_WINDOWS // Specifies that the minimum required platform is Windows 98.
#define _WIN32_WINDOWS 0x0410 // Change this to the appropriate value to target Windows Me or later.
#endif
#ifndef _WIN32_IE // Specifies that the minimum required platform is Internet Explorer 7.0.
#define _WIN32_IE 0x0700 // Change this to the appropriate value to target other versions of IE.
#endif
6. stdafx.h (Utilities/ 目录)
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//
#pragma once
#include "targetver.h"
#define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers
// Windows Header Files:
#include <windows.h>
#include <stdio.h>
// TODO: reference additional headers your program requires here
7. stdafx.cpp (Utilities/ 目录)
// stdafx.cpp : source file that includes just the standard includes
// Utilities.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information
#include "stdafx.h"
// TODO: reference any additional headers you need in STDAFX.H
// and not in this file
8. List.h
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
__declspec( dllexport ) ListNode* CreateListNode(int value);
__declspec( dllexport ) void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);
__declspec( dllexport ) void PrintListNode(ListNode* pNode);
__declspec( dllexport ) void PrintList(ListNode* pHead);
__declspec( dllexport ) void DestroyList(ListNode* pHead);
__declspec( dllexport ) void AddToTail(ListNode** pHead, int value);
__declspec( dllexport ) void RemoveNode(ListNode** pHead, int value);
9. List.cpp
// Utilities.cpp : Defines the exported functions for the DLL application.
//
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛
#include "stdafx.h"
#include "list.h"
#include <stdio.h>
#include <stdlib.h>
ListNode* CreateListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pNext = NULL;
return pNode;
}
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
if(pCurrent == NULL)
{
printf("Error to connect two nodes.
");
exit(1);
}
pCurrent->m_pNext = pNext;
}
void PrintListNode(ListNode* pNode)
{
if(pNode == NULL)
{
printf("The node is NULL
");
}
else
{
printf("The key in node is %d.
", pNode->m_nValue);
}
}
void PrintList(ListNode* pHead)
{
printf("PrintList starts.
");
ListNode* pNode = pHead;
while(pNode != NULL)
{
printf("%d ", pNode->m_nValue);
pNode = pNode->m_pNext;
}
printf("
PrintList ends.
");
}
void DestroyList(ListNode* pHead)
{
ListNode* pNode = pHead;
while(pNode != NULL)
{
pHead = pHead->m_pNext;
delete pNode;
pNode = pHead;
}
}
void AddToTail(ListNode** pHead, int value)
{
ListNode* pNew = new ListNode();
pNew->m_nValue = value;
pNew->m_pNext = NULL;
if(*pHead == NULL)
{
*pHead = pNew;
}
else
{
ListNode* pNode = *pHead;
while(pNode->m_pNext != NULL)
pNode = pNode->m_pNext;
pNode->m_pNext = pNew;
}
}
void RemoveNode(ListNode** pHead, int value)
{
if(pHead == NULL || *pHead == NULL)
return;
ListNode* pToBeDeleted = NULL;
if((*pHead)->m_nValue == value)
{
pToBeDeleted = *pHead;
*pHead = (*pHead)->m_pNext;
}
else
{
ListNode* pNode = *pHead;
while(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)
pNode = pNode->m_pNext;
if(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)
{
pToBeDeleted = pNode->m_pNext;
pNode->m_pNext = pNode->m_pNext->m_pNext;
}
}
if(pToBeDeleted != NULL)
{
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
10. 参考代码下载
项目 05_PrintListInReversedOrder 下载： 百度网盘
何海涛《剑指Offer：名企面试官精讲典型编程题》 所有参考代码下载：百度网盘
参考资料
[1] 何海涛. 剑指 Offer：名企面试官精讲典型编程题 [M]. 北京：电子工业出版社，2012. 49-53.