CodingInterviews005-从尾到头打印链表

CodingInterviews005-从尾到头打印链表.cpp

/*

题目：从尾到头打印链表
题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

*/

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

// 使用栈的入栈出栈（运行时间：3ms 占用内存：492k）
class Solution1 {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        std::stack<ListNode*> nodes;
        std::vector<int> listVector;
        ListNode* pNode = head;
        while(pNode) {
            nodes.push(pNode);
            pNode = pNode->next;
        }
        while(!nodes.empty()) {
            listVector.push_back(nodes.top()->val);
            nodes.pop();
        }
        return listVector;
    }
};

// 递归（运行时间：3ms 占用内存：360k）
class Solution2 {
public:
    vector<int> listVector;
    vector<int>& printListFromTailToHead(ListNode* head) {
        if(head) {
            if(head->next) {
                listVector = printListFromTailToHead(head->next);
            }
            listVector.push_back(head->val);
        }
        return listVector;
    }
};

// 反向迭代器（运行时间：3ms 占用内存：472k）
class Solution3 {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> listVector;
        ListNode *pNode = head;
        while (pNode) {
            listVector.push_back(pNode->val);
            pNode = pNode->next;
        }
        return vector<int>(listVector.rbegin(), listVector.rend());
    }
};

// 先让链表逆置，再顺序存储（运行时间：3ms 占用内存：476k）
class Solution4 {
public:
	ListNode * ListReverse(ListNode* head) {
		ListNode* pNode = head;
		ListNode* pPrev = nullptr;
		while (pNode) {
			ListNode* pNext = pNode->next;
			pNode->next = pPrev;
			pPrev = pNode;
			pNode = pNext;
		}
		return pPrev;
	}
	vector<int> printListFromTailToHead(ListNode* head) {
		vector<int> listVector;
		ListNode* pNode = ListReverse(head);
		while (pNode) {
			listVector.push_back(pNode->val);
			pNode = pNode->next;
		}
		return listVector;
	}
};