剑指offer-3-输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

谁借莪１个温暖的怀抱￠ 2022-03-11 02:46 66阅读 0赞

网上有些是用栈来解题的，有些是直接使用reverse翻转vector的，有些用两个vector，其中一个正序存链表的数据，再将这个vector反向赋值给另一个vector。我是用纯链表来做的。但是这个要注意：该题的head指针是包含了元素值的，之前看的博客教程和数据结构的书，头指针是不包含数据的。代码如下：

/**
    *  struct ListNode {
    *        int val;
    *        struct ListNode *next;
    *        ListNode(int x) :
    *              val(x), next(NULL) {
    *        }
    *  };
    */
    
    class Solution {
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            
            vector<int> ivec;
            if(head == NULL)
            {
                return ivec;
            }
            
            //反转
            ListNode* prev = NULL;
            ListNode* cur = head;
            ListNode* next = NULL;
    
            while(cur)
            {
                next = cur->next;
                
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            head = prev;
            
            //赋值
            ListNode *p = head;
            while(p)
            {
                ivec.push_back(p->val);
                p = p->next;
            }
            
            
            return ivec;
            
        }
    };