携手创造，一起成长！这是我参加「日新计划 8 月更文应战」的第21天，点击检查活动概况

标题

给你一个单链表的头节点 head，请你判别该链表是否为回文链表。假设是，回来 true；不然，回来 false。

示例 1：

• 输入：head = [1,2,2,1]
• 输出：true

示例 2：

• 输入：head = [1,2]
• 输出：false

方法一：将值仿制到数组中并判别数组中元素个数

思路

假设你还不太熟悉链表，下面有关于列表的概要讲述。

有两种常用的列表完结，分别为数组列表和链表。假设我们想在列表中存储值，它们是怎么完结的呢？

• 数组列表底层是运用数组存储值，我们能够经过索引在 $O(1)$ 的时间访问列表任何方位的值，这是由根据内存寻址的方法。
• 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需求 $O(n)$ 的时间，因为要经过指针获取到下一个方位的节点。

确认数组列表是否回文很简略，我们能够运用双指针法来比较两头的元素，并向中心移动。一个指针从起点向中心移动，另一个指针从结束向中心移动。这需求 $O(n)$ 的时间，因为访问每个元素的时间是 $O(1)$，而有 $n$ 个元素要访问。

但是相同的方法在链表上操作并不简略，因为不论是正向访问仍是反向访问都不是 $O(1)$。而将链表的值仿制到数组列表中是 $O(n)$，因此最简略的方法就是将链表的值仿制到数组列表中，再运用双指针法判别。

算法

一共为两个过程：

1. 仿制链表值到数组列表中。
2. 运用双指针法判别是否为回文。

第一步，我们需求遍历链表将值仿制到数组列表中。我们用 currentNode 指向当时节点。每次迭代向数组添加 currentNode.val，并更新 currentNode = currentNode.next，当 currentNode = null 时间断循环。

第二步，我们在起点放置一个指针，在结束放置一个指针，每一次迭代判别两个指针指向的元素是否相同，若不同，回来 false；相同则将两个指针向内移动，并持续判别，直到两个指针相遇。

代码

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if nil == head {
            return false
        }
        var vals: [Int] = []
        var currentNode: ListNode? = head
        while nil != currentNode {
            vals.append(currentNode!.val)
            currentNode = currentNode!.next
        }
        var i = 0
        while i < (vals.count / 2) {
            if vals[i] != vals[vals.count - 1 - i] {
                return false
            }
            i += 1
        }
        return true
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其间 $n$ 指的是链表的元素个数。

  • 第一步： 遍历链表并将值仿制到数组中，$O(n)$。
  • 第二步：双指针判别是否为回文，执行了$O(n/2)$ 次的判别，即 $O(n)$。
  • 总的时间复杂度：$O(2n)=O(n)$。

• 空间复杂度：$O(n)$，其间 $n$ 指的是链表的元素个数，我们运用了一个数组列表寄存链表的元素值。