从尾到头打印链表（C++和Python 实现）

（说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指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, );
    AddToTail(&head, );
    AddToTail(&head, );
    AddToTail(&head, );
    AddToTail(&head, );

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

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 "..\Utilities\List.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\t", 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\t", pHead->m_nValue);
    }
}

void Test(ListNode* pHead)
{
    PrintList(pHead);
    PrintListReversingly_Iteratively(pHead);
    printf("\n");
    PrintListReversingly_Recursively(pHead);
}

// 1->2->3->4->5
void Test1()
{
    printf("\nTest1 begins.\n");

    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);

    Test(pNode1);

    DestroyList(pNode1);
}

// 只有一个结点的链表: 1
void Test2()
{
    printf("\nTest2 begins.\n");

    ListNode* pNode1 = CreateListNode();

    Test(pNode1);

    DestroyList(pNode1);
}

// 空链表
void Test3()
{
    printf("\nTest3 begins.\n");

    Test(NULL);
}

int _tmain(int argc, _TCHAR* argv[])
{
    Test1();
    Test2();
    Test3();

    return ;
}

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.\n");
        exit();
    }

    pCurrent->m_pNext = pNext;
}

void PrintListNode(ListNode* pNode)
{
    if(pNode == NULL)
    {
        printf("The node is NULL\n");
    }
    else
    {
        printf("The key in node is %d.\n", pNode->m_nValue);
    }
}

void PrintList(ListNode* pHead)
{
    printf("PrintList starts.\n");

    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);
        pNode = pNode->m_pNext;
    }

    printf("\nPrintList ends.\n");
}

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.