題目描述
輸入一個(gè)鏈表的頭結(jié)點(diǎn)孽水，從尾到頭反過(guò)來(lái)打印出每個(gè)結(jié)點(diǎn)的值
實(shí)現(xiàn)思路
前端工程師看到這個(gè)題目苟耻，直接想到的就是赶站，寫個(gè)while循環(huán)來(lái)遍歷鏈表，在循環(huán)中把節(jié)點(diǎn)的值存儲(chǔ)在數(shù)組中均芽，最后在把數(shù)組倒序后贬派，遍歷數(shù)組打印每個(gè)值
如果這個(gè)題目這么簡(jiǎn)單俐芯，面試官也就不考了
如果面試官提要求說(shuō)篮绰，不許使用數(shù)組的任何方法，你會(huì)怎么解決镇眷？
由于是鏈表咬最，肯定要遍歷。遍歷的順序是從頭到尾欠动，可輸出的順序卻是從尾到頭永乌。
也就是先拿到的數(shù)據(jù)惑申，最后一個(gè)輸出。最后拿到的數(shù)據(jù)翅雏，第一個(gè)輸出圈驼。有沒(méi)有感覺(jué)跟棧的定義很像？棧就是“后進(jìn)先出”望几，題目的要求也是绩脆。
而遞歸本質(zhì)就是一個(gè)棧結(jié)構(gòu)，所以我們用遞歸來(lái)實(shí)現(xiàn)：每次遍歷時(shí)橄抹，先輸出后面的節(jié)點(diǎn)靴迫，在輸出當(dāng)前節(jié)點(diǎn)
代碼實(shí)現(xiàn)
function printListFromTailToHead(head) {
if (head.next) {
printListFromTailToHead(head.next);
}
console.log(head.val);
}
代碼看起來(lái)很清爽，但是遞歸有個(gè)問(wèn)題楼誓，當(dāng)參數(shù)很大時(shí)玉锌，會(huì)導(dǎo)致循環(huán)調(diào)用層級(jí)很深，有可能導(dǎo)致調(diào)用棧溢出疟羹。后續(xù)再討論如何優(yōu)化主守。
