本文共 2982 字，大约阅读时间需要 9 分钟。

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

解题思路

链表的遍历是从头节点开始的，而栈是先进后出的，因此我们可以将遍历到的数据先进行压栈操作，然后遍历完了之后我们进行出栈操作，则得到的结果就是我吗所需要的从尾到头打印链表的结果

C++求解

代码：

/***  struct ListNode {*        int val;*        struct ListNode *next;*        ListNode(int x) :*              val(x), next(NULL) {*        }*  };*/class Solution {
   public:    vector
   
     printListFromTailToHead(ListNode* head) {
           ListNode *temp;        temp=head;        stack
    
      s;        vector
     
       res;        while(temp){
               s.push(temp->val);            temp=temp->next;        }        while(!s.empty()){
               res.push_back(s.top());            s.pop();        }        return res;    }};
     
    
   

运行时间：3ms占用内存：376k

拓展应用–两数相加

这类逆序的问题都可以用栈来解决，这里举一个两数相加的例子：

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储 一位

数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

解题代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
           stack 
   
     t1,t2,s1,s2,res;        int carry=0,temp;        while(l1){
               t1.push(l1->val);            l1=l1->next;        }        while(l2){
               t2.push(l2->val);            l2=l2->next;        }        while(!t1.empty()){
               s1.push(t1.top());            t1.pop();        }        while(!t2.empty()){
               s2.push(t2.top());            t2.pop();        }        while(!s1.empty()||!s2.empty()||carry){
               if(!s1.empty()&&!s2.empty()){
                   temp=s1.top()+s2.top()+carry;                if(temp>9){
                       carry=1;                    res.push(temp-10);                }else{
                       carry=0;                    res.push(temp);                }                s1.pop();                s2.pop();            }else if(!s1.empty()){
                   temp=s1.top()+carry;                if(temp>9){
                       carry=1;                    res.push(temp-10);                }else{
                       carry=0;                    res.push(temp);                }                s1.pop();            }else if(!s2.empty()){
                   temp=s2.top()+carry;                if(temp>9){
                       carry=1;                    res.push(temp-10);                }else{
                       carry=0;                    res.push(temp);                }                s2.pop();            }else if(carry){
                   res.push(carry);                carry=0;            }        }        ListNode *head,*t,*ptr;        head=NULL;        while(!res.empty()){
               ptr=new ListNode(res.top());            ptr->next=head;            head=ptr;            res.pop();        }        return head;    }};
   

这里只作为一个应用的例子讲解，并不是最优解法

转载地址：https://blog.csdn.net/Jeaten/article/details/107935354 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！