回文链表
给定一个链表的 头节点head
, 请判断其是否为回文链表。
如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。
示例 1:
输入: head = [1,2,3,3,2,1]
输出: true
示例 2:
输入: head = [1,2]
输出: false
解题思路
我们做过数组列表是否回文的题目,如果是数组时我们可以使用双指针法来比较两端的元素,并向中间移动。一个指针从起点向中间移动,另一个指针从终点向中间移动。
对于链表我们可以将链表的值复制到数组列表中,再使用双指针法来检查是否为回文。我们在起点放置一个指针,在结尾放置一个指针,每一次迭代判断两个指针指向的元素是否相同,若不同,返回 false;相同则将两个指针向内移动,并继续判断,直到两个指针相遇。
具体步骤如下:
- 第一步:初始化一个数组变量,用于存储链表的值
- 第二步: 遍历每一个链表节点,如果不是null就把当前节点的值存到数组里
- 第三步:使用for循环遍历数组,初始化两个索引,一个指向开始,一个指向结束,两个指针向数组中间聚拢
- 第四步: 循环内判断两个指针指向的值是否相同,如不不相同说明就不是回文,则返回false
var isPalindrome = function(head) { const vals = []; while (head !== null) { vals.push(head.val); head = head.next; } for (let i = 0, j = vals.length - 1; i < j; i++, j--) { if (vals[i] !== vals[j]) { return false; } } return true; };