C++——输入链表，逆序输出list

青旅半醒 2022-11-25 15:28 173阅读 0赞

## 题目要求： ##

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

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
    class Solution { 
    public:
    	vector<int> printListFromTailToHead(ListNode* head) { 
    	}
    }

## 解题思路 ##

### 方法1 ###

1.  遍历链表，记录链表大小。
2.  创建跟链表大小一样的vecter list
3.  将链表第一个元素放入list最后一个位置，并更新链表=链表->next

### 方法2 ###

也可以使用堆栈：

1.  将链表当前数值放入堆stack a，链表=链表->next，a.push(1);
2.  计算堆栈大小a.size();
3.  将堆栈a的数据pop出来

## 参考代码： ##

// 方法1
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    struct ListNode { 
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    		val(x), next(NULL) { 
    	}
    };
    
    void list_print(ListNode * list) { 
    
    	if (list != NULL) { 
    		while (list->next != NULL) { 
    			cout << list->val << " ";
    			list = list->next;
    		}
    		cout << list->val << endl;
    	}
    }
    
    class Solution { 
    public:
    	vector<int> printListFromTailToHead(ListNode* head) { 
    		ListNode* head_cp = head;
    		if (head != NULL)
    		{ 
    			int count = 1;
    
    			while (head->next != NULL) { 
    				head = head->next;
    				count++;
    			}
    
    			vector<int> list(count);
    			for (int i = count - 1; i >= 0; i--) { 
    				list[i] = head_cp->val;
    				head_cp = head_cp->next;
    			}
    			return list;
    		}
    		vector<int> a;
    		return a;
    	}
    };
    
    int main() { 
    	ListNode* list = new ListNode(0);
    	ListNode* head = list;
    
    	if (list == NULL) 
    		return 0;
    
    	for (int i = 0; i < 20; i++) { 
    		ListNode* node = new ListNode(i+1);
    		list->next = node;
    		list = list->next;
    	}
    
    	list_print(head);
    
    	Solution s;
    
    	vector<int> re = s.printListFromTailToHead(head);
    	for (int i = 0; i < re.size(); i++) { 
    		cout << re[i] << " ";
    	}
    	cout << endl;
    }