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

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

于是我在leetcode 上找了一下這道題，看看我能不能寫得出來。

題目的要求很簡單：

反轉(zhuǎn)一個單鏈表。
示例:
輸入: 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;

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

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

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

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

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

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

我們先來看一下它的數(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] } } }

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

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

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

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;
};

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

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

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;
};

這回就過了。

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

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

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 });
    }
}

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

遞歸成功之后，后面的事情就相對簡單了。

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

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ù)來表示：

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ù)還有一個特色是如果你只有一條return語句的話，連外面的花括號和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)一步簡化，我們把上面的函數(shù)再精簡，這時候你仔細(xì)觀察的話，會發(fā)現(xiàn)第一個函數(shù)和第二個函數(shù)很類似，都是在調(diào)用第二個函數(shù)，那么我們能不能精簡一下把它們合并呢？我們先把第一個函數(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 }));

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

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

這時候我們的兩個函數(shù)長的基本一致了，我們來把它們合并一下：

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

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

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