检查链表在 JavaScript 中是否是回文

Question

我在 JavaScript 中编写了以下函数来检查单向链表是否是回文。但是，我在 10 次测试中有 2 次失败，我不知道为什么。

这是我正在接受的测试。

1. l： [0， 1， 0]
l： [1， 1000000000， -1000000000， -1000000000，
2. 1000000000， 1]

对于回文，两者都应该返回 true，但我的函数返回 false。

这是我的代码：

function isListPalindrome(l) {
let curr = l;
let arr = [];

if (l == null)
return true;

// push all elements of l into the stack.
// a stack in JS is an array.
while(curr != null){
arr.push(l.value);

// move ahead:
curr = curr.next;
}

let curr2 = l;
// Traverse the list again & check by popping from the stack:
while(curr2 != null){

// get the top most element on the stack:
let num = arr.shift();

// check if the node data isn't the same as the element popped:
if (curr2.value != num){
return false;
}

// move ahead:
curr2 = curr2.next;
}
return true;
}

谢谢！

Answer 1

在第一个 while 循环中，您正在推动l.value，但l没有递增，因此它将相同的值推送到arr。

你现在有arr，它应该是反向的l。在第二个 while 循环中，不使用 arr.shift(( 使用 arr.pop((。这将从arr堆栈中删除第一个元素。请记住，堆栈是先进后出的。

另请注意，当您比较列表的正面和背面时，您将到达一个无关紧要的点，即中间点。一旦您知道前向列表中的一半值与反向列表中的值相同，您就知道其余的值将通过测试。

这是它应该的样子。你应该试着弄清楚如何自己做赔率。

function isListPalindrome(l) {
let curr = l;
let arr = [];
if (l == null)
return true;
// push all elements of l into the stack.
// a stack in JS is an array.
while(curr != null){
arr.push(curr.value);
// move ahead:
curr = curr.next;
}
let curr2 = l;
let length = arr.length;
// Traverse the list again & check by popping from the stack:
while(curr2 != null){
// get the top most element on the stack:
let lastNum = arr.pop();
// check if the node data isn't the same as the element popped:
if (curr2.value != lastNum){
return false;
}
// Half way point for evens
if (length / 2 === arr.length) {
return true;
}
// move ahead:
curr2 = curr2.next;
}
return true;
}

Answer 2

通过将值推送到数组然后检查数组是否为回文来解决将具有S:O(N). 反转后半部分然后遍历将有S:O(1). 两者T:O(N)相同：

var isPalindrome = function (head) {
let fast_pointer = head;
let slow_pointer = head;
// when fast_ppointer reaches to the tail, slow_pointer will be in the middle
while (fast_pointer && fast_pointer.next) {
fast_pointer = fast_pointer.next.next;
slow_pointer = slow_pointer.next;
}
// now, slow_pointer is in the middle and we reverse from slow_pointer till the head
let prev = null;
while (slow_pointer) {
// slow_pointer=slow_pointer.next how we iterate in linked lists.
// so make sure we keep a reference to the next iteration
temp = slow_pointer.next;
slow_pointer.next = prev;
prev = slow_pointer;
slow_pointer = temp;
}
let left = head;
let right = prev;
while (right) {
if (left.val !== right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
};

Answer 3

var isPalindrome = function (head) {
let values = [];
while (head) {
values.push(head.val);
head = head.next;
}
let rev = [];
head.map((e) => {
rev.unshift(e);
});
if (values.every((val, index) => val === rev[index])) {
return true;
} else {
return false;
}
};

Answer 4

class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
const is_palindromic_linked_list = function (head) {
let front = head;
const traverse = (node) => {
if (!node) return true;
//reverse the LL
const reverse = traverse(node.next);
//check value if they are equal
const valChecker = front.value == node.value;
front = front.next;
return reverse && valChecker;
}
return traverse(head)
};
head = new Node(2)
head.next = new Node(4)
head.next.next = new Node(6)
head.next.next.next = new Node(4)
head.next.next.next.next = new Node(2)
console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)
head.next.next.next.next.next = new Node(2)
console.log(`Is palindrome: ${is_palindromic_linked_list(head)}`)

Answer 5

我将列表的所有元素推送到一个数组中，然后将带有连接函数的数组转换为字符串，以便我可以比较字符串是否与使用反向函数的逆字符串相同，如果是，则它是一个回文

function isListPalindrome(l) {
if(l === null) return true;
let array =[];
let current = l;
while (current != null){
array.push(current.value);
current = current.next
}
if(array.join('')=== array.reverse().join('')) return true; 
return false
}