【剑指Offer第三题】从尾到头打印链表-创新互联

题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

网站的建设创新互联建站专注网站定制,经验丰富,不做模板,主营网站定制开发.小程序定制开发,H5页面制作!给你焕然一新的设计体验!已为成都铜雕雕塑等企业提供专业服务。

注:设链表长度为n。语言:C++


链表结点数据结构规定如下:

*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };

解法1:正向遍历,借助反向迭代器实现序列逆置(C++特性)。

vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        vector array;
        while(p != NULL)
        {
            array.push_back(p->val);
            p = p->next;
        }
        return vector(array.rbegin(), array.rend());
    }

时间复杂度:O(n),空间复杂度:O(1)


解法2:借助栈先进后出的特性,将链表结点先入栈后出栈,再压入序列中。

vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        stack s;
        while(p != NULL)
        {
            s.push(p->val);
            p = p->next;
        }
        p = head;
        vector array;
        while(p != NULL)
        {
            array.push_back(s.top());
            s.pop();
            p = p->next;
        }
        return array;
    }

时间复杂度:O(n),空间复杂度:O(n)


解法3:递归

    vector array;
    vector printListFromTailToHead(ListNode* head) {
        ListNode *p;
        p = head;
        if(head != NULL)
        {
            if(head->next != NULL)
                printListFromTailToHead(head->next);
            array.push_back(head->val);
        }
        return array;
    }

时间复杂度:O(n),空间复杂度:O(n)

另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


文章标题:【剑指Offer第三题】从尾到头打印链表-创新互联
文章链接:http://myzitong.com/article/eiece.html