题目:给你一个单链表的头节点 head ,请你判断该链表是否为
回文链表
。如果是,返回 true ;否则,返回 false 。
PS: 回文 序列是向前和向后读都相同的序列。
解题思路:
遍历链表,将每个元素存放入一个新的数组中。遍历完成后,再用两个指针前后遍历数组来判断两个数字是否相等。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
const arr = new Array();
while(head) {
arr.push(head.val);
head = head.next;
}
let i = 0;
let j = arr.length - 1;
while(i < j){
if(arr[i] === arr[j]){
i++;
j--;
} else {
return false;
}
}
return true;
}
这样的时间复杂度和空间复杂度都为O(n)
。
** 可以尝试着把空间复杂度降到O(1):
不借助额外的数组,用双指针和原地修改链表的方法。我们将链表分成前后两个部分,反转后半部分的链表,然后通过双指针判断是否是回文。
思路:
使用快慢指针找到链表的中间节点。
反转后半部分的链表。
比较前半部分和后半部分的节点值。
恢复链表(可选,面试时有时候要求恢复原链表)。