您好,登錄后才能下訂單哦!
題目描述
輸入一個(gè)鏈表,按鏈表從尾到頭的順序返回一個(gè)ArrayList。
注:設(shè)鏈表長(zhǎng)度為n。語(yǔ)言:C++
鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)規(guī)定如下:
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
解法1:正向遍歷,借助反向迭代器實(shí)現(xiàn)序列逆置(C++特性)。
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
vector<int> array;
while(p != NULL)
{
array.push_back(p->val);
p = p->next;
}
return vector<int>(array.rbegin(), array.rend());
}
時(shí)間復(fù)雜度:O(n),空間復(fù)雜度:O(1)
解法2:借助棧先進(jìn)后出的特性,將鏈表結(jié)點(diǎn)先入棧后出棧,再壓入序列中。
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
stack<int> s;
while(p != NULL)
{
s.push(p->val);
p = p->next;
}
p = head;
vector<int> array;
while(p != NULL)
{
array.push_back(s.top());
s.pop();
p = p->next;
}
return array;
}
時(shí)間復(fù)雜度:O(n),空間復(fù)雜度:O(n)
解法3:遞歸
vector<int> array;
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
if(head != NULL)
{
if(head->next != NULL)
printListFromTailToHead(head->next);
array.push_back(head->val);
}
return array;
}
時(shí)間復(fù)雜度:O(n),空間復(fù)雜度:O(n)
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。