摘要：但是題目非要弄成鏈表的形式，說(shuō)實(shí)在的，我真沒(méi)有見(jiàn)過(guò)前端什么地方還需要用鏈表這種結(jié)構(gòu)的除了面試的時(shí)候，所以說(shuō)這種題目對(duì)于實(shí)際工作是沒(méi)什么用處的，但是腦筋急轉(zhuǎn)彎的智商題既然這樣出了，我們就來(lái)看看怎么解決它吧。

今天在知乎上看到一個(gè)回答《為什么前端工程師那么難招？》，作者提到說(shuō)有很多前端工程師甚至連單鏈表翻轉(zhuǎn)都寫(xiě)不出來(lái)。說(shuō)實(shí)話(huà)，來(lái)面試的孩子們本來(lái)就緊張，你要冷不丁問(wèn)一句單鏈表翻轉(zhuǎn)怎么寫(xiě)，估計(jì)很多人都會(huì)蒙掉。

于是我在leetcode 上找了一下這道題，看看我能不能寫(xiě)得出來(lái)。

題目的要求很簡(jiǎn)單：

反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

最后的解決就是這樣的一行代碼：

const reverseList = (head, q = null) => head !== null ? reverseList(head.next, { val: head.val, next: q }) : q;

答案并不重要，有意思的是整個(gè)的解題思路。

在解題之前，我們先來(lái)聊聊算法。嚴(yán)格來(lái)說(shuō)，單鏈表翻轉(zhuǎn)這種問(wèn)題只是對(duì)于鏈表這種數(shù)據(jù)結(jié)構(gòu)的一種操控而已，根本談不上是什么算法。當(dāng)然，寬泛地來(lái)說(shuō)，只要涉及到循環(huán)和遞歸的都把它歸入到算法也可以。在這里，我們采用一種寬容的定義。

算法需要背嗎？我覺(jué)得算法是不需要背的，你也不可能背的下來(lái)，光leetcode就有上千道題目，并且還在增加，怎么可能背的下來(lái)？所以對(duì)于現(xiàn)階段的程序員來(lái)說(shuō)，算法分為兩類(lèi)，一類(lèi)是你自己能推算出來(lái)的，這種不用背，一類(lèi)是你推算不出來(lái)的，比如KMP算法，這種也不用背，需要的時(shí)候直接Google就可以了。特別是對(duì)于前端以及80%的后端程序員來(lái)說(shuō)，你需要什么算法，就直接使用現(xiàn)在的庫(kù)就行了，數(shù)組排序直接array.sort就可以，誰(shuí)沒(méi)事還非要去寫(xiě)一個(gè)快速排序？

那為什么面試前端的時(shí)候還必須要考算法？這個(gè)道理基本上類(lèi)似于通過(guò)考腦筋急轉(zhuǎn)彎來(lái)測(cè)試智商一樣，實(shí)際工作中是完全用不上的，就像高考的時(shí)候考一大堆物理、化學(xué)、生物，恨不得你上知天文，下知地理，上下五千年，精通多國(guó)語(yǔ)言，但其實(shí)你參加工作以后發(fā)現(xiàn)根本用不上一樣，這其實(shí)就是一個(gè)智商篩子，過(guò)濾一下而已。

所以，別管工作中用不用得到，如果你想通過(guò)這道篩子的話(huà)，算法的東西多少還是應(yīng)該學(xué)習(xí)一些的。

說(shuō)實(shí)話(huà)，我剛做這道題的時(shí)候，我也有點(diǎn)蒙。雖然上學(xué)的時(shí)候?qū)W過(guò)數(shù)據(jù)結(jié)構(gòu)，鏈表、堆棧、二叉樹(shù)這些東西，但這么多年實(shí)際工作中用的很少，幾乎都快忘光了，不過(guò)沒(méi)關(guān)系，我們就把它當(dāng)成是腦筋急轉(zhuǎn)彎來(lái)做一下好了。

我們先來(lái)看一下它的數(shù)據(jù)結(jié)構(gòu)是什么樣的：

var reverseList = function(head) {
    console.log(head);
};

ListNode {  
  val: 1, next: ListNode {
    val: 2, next: ListNode {
      val: 3, next: [ListNode] } } }

一個(gè)對(duì)象里包含了兩個(gè)屬性，一個(gè)屬性是val，一個(gè)屬性是next，這樣一層一層循環(huán)嵌套下去。

通常來(lái)講，在前端開(kāi)發(fā)當(dāng)中，我們最常用的是數(shù)組。如果是用數(shù)組的話(huà)，就太簡(jiǎn)單了，js數(shù)組自帶reverse方法，直接array.reverse反轉(zhuǎn)就行了。但是題目非要弄成鏈表的形式，說(shuō)實(shí)在的，我真沒(méi)有見(jiàn)過(guò)前端什么地方還需要用鏈表這種結(jié)構(gòu)的（除了面試的時(shí)候），所以說(shuō)這種題目對(duì)于實(shí)際工作是沒(méi)什么用處的，但是腦筋急轉(zhuǎn)彎的智商題既然這樣出了，我們就來(lái)看看怎么解決它吧。

首先想到的，這肯定是一個(gè)while循環(huán)，循環(huán)到最后，發(fā)現(xiàn)next是null就結(jié)束，這個(gè)很容易想。但關(guān)鍵是怎么倒序呢？這個(gè)地方需要稍微動(dòng)一下腦子。我們觀察一下，倒序之后的結(jié)果，1變成了最后一個(gè)，也就是說(shuō)1的next是null，而2的next是1。所以我們一上來(lái)先構(gòu)建一個(gè)next是null的1結(jié)點(diǎn)，然后讀到2的時(shí)候，把2的next指向1，這樣不就倒過(guò)了嗎？所以一開(kāi)始的程序?qū)懗鰜?lái)是這樣的：

var reverseList = function(head) {
  let p = head;
  let q = { val: p.val, next: null };
  while (p.next !== null) {
    p = p.next;
    q = { val: p.val, next: q };
  }
  return q;
};

先初始化了一個(gè)q，它的next是null，所以它就是我們的尾結(jié)點(diǎn)，然后再一個(gè)一個(gè)指向它，這樣整個(gè)鏈表就倒序翻轉(zhuǎn)過(guò)來(lái)了。

第一個(gè)測(cè)試用例沒(méi)有問(wèn)題，于是就提交了，但是提交完了發(fā)現(xiàn)不對(duì)，如果head本身是null的話(huà)，會(huì)報(bào)錯(cuò)，所以修改了一下：

var reverseList = function(head) {
  let p = head;
  if (p === null) {
    return null;
  }
  let q = { val: p.val, next: null };
  while (p.next !== null) {
    p = p.next;
    q = { val: p.val, next: q };
  }
  return q;
};

這回就過(guò)了。

解決是解決了，但是這么長(zhǎng)的代碼，明顯不夠優(yōu)雅，我們嘗試用遞歸的方法對(duì)它進(jìn)一步優(yōu)化。

如果有全局變量的話(huà)，遞歸本身并不復(fù)雜。但因?yàn)?b>leetcode里不允許用全局變量，所以我們只好構(gòu)造一個(gè)雙參數(shù)的函數(shù)，把倒序之后的結(jié)果也作為一個(gè)參數(shù)傳進(jìn)去，這樣剛一開(kāi)始的時(shí)候q是一個(gè)null，隨著遞歸的層層深入，q逐漸包裹起來(lái)，直到最后一層：

const reverseList = function(head) {
    let q = null;
    return r(head, q);
}
const r = function(p, q) {
    if (p === null) {
        return q;
    } else {
        return r(p.next, { val: p.val, next: q });
    }
}

這里我們終于理清了出題者的思路，用遞歸的方式我們可以把這個(gè)if判斷作為整個(gè)遞歸結(jié)束的必要條件。如果p不是null，那么我們就再做一次，把p的下一個(gè)結(jié)點(diǎn)放進(jìn)來(lái)，比如說(shuō)1的下一個(gè)是2，那么我們這時(shí)候就從2開(kāi)始執(zhí)行，直到最后走到5，5的下一個(gè)結(jié)點(diǎn)是null，然后我們退回上一層，這樣一層層鉆下去，最后再一層層返回來(lái)，就完成了整個(gè)翻轉(zhuǎn)的過(guò)程。

遞歸成功之后，后面的事情就相對(duì)簡(jiǎn)單了。

怎么能把代碼弄簡(jiǎn)短一些呢？我們注意到這里這個(gè)if語(yǔ)句里面都是直接return，那我們干脆直接做個(gè)三元操作符就好了：

const reverseList = function(head) {
    let q = null;
    return r(head, q);
}
const r = function(p, q) {
    return p === null ? q : r(p.next, { val: p.val, next: q });
}

更進(jìn)一步，我們用箭頭函數(shù)來(lái)表示：

const reverseList = (head) => {
    let q = null;
    return r(head, q);
}
const r = (p, q) => {
    return p === null ? q : r(p.next, { val: p.val, next: q });
}

箭頭函數(shù)還有一個(gè)特色是如果你只有一條return語(yǔ)句的話(huà)，連外面的花括號(hào)和return關(guān)鍵字都可以省掉，于是就變成了這樣：

const reverseList = (head) => {
    let q = null;
    return r(head, q);
}
const r = (p, q) => (p === null ? q : r(p.next, { val: p.val, next: q }));

這樣是不是看著就短多了呢？但是還可以更進(jìn)一步簡(jiǎn)化，我們把上面的函數(shù)再精簡(jiǎn)，這時(shí)候你仔細(xì)觀察的話(huà)，會(huì)發(fā)現(xiàn)第一個(gè)函數(shù)和第二個(gè)函數(shù)很類(lèi)似，都是在調(diào)用第二個(gè)函數(shù)，那么我們能不能精簡(jiǎn)一下把它們合并呢？我們先把第一個(gè)函數(shù)變換為和第二函數(shù)的參數(shù)數(shù)目一致的形式：

const reverseList = (head, q) => r(head, q);
const r = (p, q) => (p === null ? q : r(p.next, { val: p.val, next: q }));

但這時(shí)候出現(xiàn)了一個(gè)問(wèn)題，如果q沒(méi)有初始值的話(huà)，它是undefined，不是null，所以我們還需要給q一個(gè)初始值：

const reverseList = (head, q = null) => r(head, q);
const r = (p, q) => (p === null ? q : r(p.next, { val: p.val, next: q }));

這時(shí)候我們的兩個(gè)函數(shù)長(zhǎng)的基本一致了，我們來(lái)把它們合并一下：

const reverseList = (head, q = null) => (head === null ? q : reverseList(head.next, { val: head.val, next: q }));

看，這樣你就得到了一個(gè)一行代碼的遞歸函數(shù)可以解決單鏈表翻轉(zhuǎn)的問(wèn)題。

實(shí)話(huà)說(shuō)，即使是像我這樣有多年經(jīng)驗(yàn)的程序員，要解決這樣的一個(gè)問(wèn)題，都需要這么長(zhǎng)的時(shí)間這么多步驟才能優(yōu)化完美，更何況說(shuō)一個(gè)大學(xué)剛畢業(yè)的孩子，很難當(dāng)場(chǎng)就一次性回答正確，能把思路說(shuō)出來(lái)就很不容易了，但你可以從這個(gè)過(guò)程中看到程序代碼是如何逐漸演進(jìn)的。背誦算法沒(méi)有意義，我覺(jué)得我們更多需要的是這一個(gè)思考的過(guò)程，畢竟編程是一個(gè)腦筋急轉(zhuǎn)彎的過(guò)程，不是唐詩(shī)三百首。