前端面试中，算法题也是特别常见的类型，我们将在未来新增一个LeetCode的专栏，给大家讲解一些常见算法题的解题思路。

为何要刷算法题

刷题刷题，从“刷”字就能看出其中的机械性和应试性，但这就是几乎所有互联网公司面试中的一环。

尽管面试者可能也对这种考察方式不是很满意，可在没有更好的方式之前，这个现状会一直保持下去。我们改变不了这个现状，那就适应它吧。

来说说 Leetcode 试题的几个特点，可能也适用于大部分面试题：

• 问题背景简单：问题描述都比较简单几句话就能说清，只有少部分题目比较复杂比较难，例如基于棋盘、柱型图、正则表达式等等。
• 数据结构选定：大多直接给定数据结构，在其上设计一个简单的算法。当然这不绝对，当题目对时间复杂度要求很高时，就要用空间换时间，这时也是要选取额外的数据结构的。
• 代码量小：一般在30-40行左右，因为面试时还要分析性能和证明正确性，所以不太可能让我们去写很多代码的。
• 考察基础：既然问题描述简单、数据结构给定、代码量还小，那还考什么呢？
• 基础数据结构：真的是基础，80%～90%都围绕着数组、链表、树、字符串进行。图很少，高级数据结构更是没有。有应该也只是考知识面吧，不可能让现场实现。
• 常用算法设计：以二分查找、快速排序、归并排序为骨架扩展，活用哈希，应用分治、贪心、组合算法、动态规划等重要设计方法。同样地，高级的像什么随机化啊、外部存储、并行算法都没有。
• 简单分析能力：能在实现之后给出执行性能和正确性的分析和理由。
• 逻辑思维能力（小逻辑）：在前两者基础上写代码，也就是所谓的小逻辑，需要的就是比较强的逻辑思维、代码熟练度。
• 考虑周全度（Corner Case）：题目不提的东西不代表不要求，所以各种Corner Case都要考虑到，不然在 Leetcode 上提交时就会被打回，面试时可能也会被质疑。

废话不多说，今天先给大家带来一道比较基础的题目 —— 回文链表。

题目

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

题目简析

在解题之前，我们首先需要理解题目的含义。首先需要理解什么是回文链表。回文一词最初出现在文学作品中，下面是维基百科给出的回文的定义。

回文，亦称回环，是正读反读都能读通的句子，亦有将文字排列成圆圈者，是一種修辭方式和文字游戏。

上面定义可能不太容易理解，简单的可以理解为正读和反读都一样的句子。为了便于理解下面给出几个简单例子。

上海自来水来自海上

黄山落叶松叶落山黄

回文链表的概念与此类似，也就是正向和反向遍历，序列一样的链表。

解题方法一

利用链表的后续遍历，使用函数调用栈作为后序遍历栈，来判断是否回文

var isPalindrome = function(head) {
    let left = head;
    function traverse(right) {
        if (right == null) return true;
        let res = traverse(right.next);
        res = res && (right.val === left.val);
        left = left.next;
        return res;
    }
    return traverse(head);
};

解题方法二

通过快、慢指针找链表中点，然后反转链表，比较两个链表两侧是否相等，来判断是否是回文链表

var isPalindrome = function(head) {
    // 反转 slower 链表
    let right = reverse(findCenter(head));
    let left = head;
    // 开始比较
    while (right != null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
}
function findCenter(head) {
    let slower = head, faster = head;
    while (faster && faster.next != null) {
        slower = slower.next;
        faster = faster.next.next;
    }
    // 如果 faster 不等于 null，说明是奇数个，slower 再移动一格
    if (faster != null) {
        slower = slower.next;
    }
    return slower;
}
function reverse(head) {
    let prev = null, cur = head, nxt = head;
    while (cur != null) {
        nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}