从头到尾打印链表详解编程语言

题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表的定义如下：

typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode;

【解题思路】（递归）
先递归出后面的节点，在输出节点本身。不足：当链表比较长时，会使函数调用层级比较深而导致函数调用栈溢出。

【代码】

void ReversePrint(pList phead) 
{ 
    if (phead != NULL) 
    { 
        if (phead->next) 
        { 
            ReversePrint(phead->next); 
        } 
        printf("%d   ", phead->data); 
    } 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
    assert(pplist); 
    *pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
    pNode cur = *pplist; 
    pNode pnode = NULL; 
    assert(pplist); 
    pnode = (pNode)malloc(sizeof(Node)); 
    if (pnode == NULL) 
    { 
        perror("PushBack::malloc"); 
        exit(EXIT_FAILURE); 
    } 
    pnode->data = x; 
    pnode->next = NULL; 
    if (cur == NULL) 
    { 
        *pplist = pnode; 
    } 
    else 
    { 
        while (cur->next != NULL) 
        { 
            cur = cur->next; 
        } 
        cur->next = pnode; 
    } 
} 
 
void Display(pList plist) 
{ 
    pNode cur = plist; 
    while (cur) 
    { 
        printf("%d-->", cur->data); 
        cur = cur->next; 
    } 
    printf("over/n"); 
} 
 
 
void Destroy(pList *pplist) 
{ 
    pNode cur = *pplist; 
    assert(pplist); 
    while (cur) 
    { 
        pNode del = cur; 
        cur = cur->next; 
        free(del); 
    } 
    *pplist = NULL; 
} 
 
void ReversePrint(pList phead) 
{ 
    if (phead != NULL) 
    { 
        if (phead->next) 
        { 
            ReversePrint(phead->next); 
        } 
        printf("%d   ", phead->data); 
    } 
} 
 
void test1() 
{ 
    pList plist; 
    pNode ret = NULL; 
    InitLinkList(&plist); 
    PushBack(&plist, 1); 
    PushBack(&plist, 2); 
    PushBack(&plist, 3); 
    PushBack(&plist, 4); 
    PushBack(&plist, 5); 
    PushBack(&plist, 6); 
    Display(plist); 
    ReversePrint(plist); 
    Destroy(&plist); 
} 
 
int main() 
{ 
    test1(); 
    system("pause"); 
    return 0; 
}

运行结果：

【附加】（栈方法）
每经过一个节点的时候把节点放到一个栈中，遍历完节点后再从栈顶开始逐个输出节点的值。

【代码】

void ReversePrint(pList phead) 
{ 
    std::stack<pList>nodes; 
    pNode pnode = phead; 
    while (pnode != NULL) 
    { 
        nodes.push(pnode); 
        pnode = pnode->next; 
    } 
    while (!nodes.empty()) 
    { 
        pnode = nodes.top(); 
        printf("%d/t", pnode->data); 
        nodes.pop(); 
    } 
}