从尾到头打印链表--《剑指offer》

2021年11月25日 阅读数:4
这篇文章主要向大家介绍从尾到头打印链表--《剑指offer》,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目:很是easy,就是题目,将链表从尾到头打印出来node

可能咱们首先想到的是将链表进行遍历,将以前的訪问的数据进行保存,最后进行反向输出,可是保存数据的空间是个问题;或者是咱们将整个链表进行反向操做,将整个链表进行逆置,可是咱们仅仅是进行打印操做而已,改变链表不合适吧...ios

事实上这时候应该想到了,用栈:既然是逆置,和栈的功能不就不谋而合吗,后进先出,进行反向打印。ide

//2014-5-18
//反向输出链表
#include <iostream>
#include <cstdlib>
#include <stack>

using namespace std;

typedef struct Node
{
    int data;
    struct Node *next;  /* 指向下个节点 */
} Node, *LinkNode;

void Create(LinkNode &head)
{
    head = (LinkNode) malloc(sizeof(Node));
    head->next = NULL;
}

void Insert(LinkNode &head, int i)
{
    if(head -> next == NULL)
    {
        LinkNode p = (LinkNode) malloc(sizeof(Node));
        p->data = i;
        p->next = head->next;
        head->next = p;
        return;
    }
    LinkNode p = head;
    while(p->next != NULL)
    {
        p = p->next;
    }
    LinkNode q = (LinkNode) malloc(sizeof(Node));
    q->data = i;
    q->next = p->next;
    p->next = q;
    //free(q);
    return;
}

void OppoLink(const LinkNode &L)
{
    if(L == NULL)
        return;
    LinkNode p = L->next;
    stack<int> node;
    while(p != NULL)
    {
        node.push(p->data);
        p = p->next;
    }

    while(!node.empty())
    {
        cout << node.top() << "  ";
        node.pop();
    }
    cout << endl;
}

int main()
{
    LinkNode L;

    Create(L);
    for(int i = 0; i < 10; i++)
    {
        Insert(L, i);
    }

    OppoLink(L);
    return 0;
}
输出例如如下:
从尾到头打印链表--《剑指offer》_ios

书中也是如我这般的,只是对于栈的处理不一样,我是使用stack<int> node;进行数据存储,而书中则是使用节点存储,只是我想这应该差点儿相同吧...(详细我也不知道,假设有什么见解的但愿指出)spa

书中给出例如如下一段话:blog

从尾到头打印链表--《剑指offer》_数据_02

这个我却是真没想到,只是依照提示递归实现了:递归

void OppoLink(LinkNode L)
{
    if(L!=NULL)
    {
        if(L->next != NULL)
        {
            OppoLink(L->next);
        }
        cout << L->data << " ";
    }
}
在调用的时候用OppoLink(L->next),因为我建立的链表有个头结点,固然,它里面的数据很是意外。。。

只是对于递归你们确定知道,层数深了的话,后果很是可怕,因此我想用栈应该会更好一些。it


O(∩_∩)O欢迎不吝赐教啦....io