一、leetcode算法
1、回文链表
1.1、题目
给你一个单链表的头节点 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 时停止循环。
执行第二步的最佳方法取决于你使用的语言。在 Python 中，很容易构造一个列表的反向副本，也很容易比较两个列表。而在其他语言中，就没有那么简单。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇。
1.3、答案
class Solution { public boolean isPalindrome(ListNode head) { List<Integer> vals = new ArrayList<Integer>(); // 将链表的值复制到数组中 ListNode currentNode = head; while (currentNode != null) { vals.add(currentNode.val); currentNode = currentNode.next; } // 使用双指针判断是否回文 int front = 0; int back = vals.size() - 1; while (front < back) { if (!vals.get(front).equals(vals.get(back))) { return false; } front++; back--; } return true; } }
