题目

给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。

示例 1：

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

示例 2：

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

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

思路

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

有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢？

• 数组列表底层是使用数组存储值，我们可以通过索引在 的时间访问列表任何位置的值，这是由基于内存寻址的方式。
• 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 的时间，因为要通过指针获取到下一个位置的节点。

确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。这需要 的时间，因为访问每个元素的时间是 ，而有 个元素要访问。

然而同样的方法在链表上操作并不简单，因为不论是正向访问还是反向访问都不是 。而将链表的值复制到数组列表中是 ，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法判断。

算法

一共为两个步骤：

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

复杂度分析

• 时间复杂度：，其中 指的是链表的元素个数。

  • 第一步： 遍历链表并将值复制到数组中，。
  • 第二步：双指针判断是否为回文，执行了 次的判断，即 。
  • 总的时间复杂度：。

• 空间复杂度：，其中 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。