检查回文链表
Check Palindrome Linked List
我打算把原来的LinkedList反转过来和反转过来的对比一下。如果相同 return 为真。但是,我一直得到错误的结果。我哪里做错了?
var isPalindrome = function(head) {
if(head == null || head.next == null) return true;
let reversedHead = reverse(head)
let count = 0
while (head != null && reversedHead != null) {
if(head.val != reversedHead.val) {
return false
}
head = head.next
reversedHead = reversedHead.next
}
if (head == null && reversedHead == null){
return true
} else {
return false
}
};
var reverse =(head)=> {
let prev = null
let next = new ListNode()
let curr = new ListNode()
curr = head
while(curr){
next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
调用后:
let reversedHead = reverse(head)
您将颠倒列表,即头部变成了尾部,尾部的下一个引用为空。因此你的循环将很快结束,如下所示:
head = head.next
...head
将是 null
.
你需要重新考虑算法。有几种方法可以做到...
而不是 inplace 反转,你可以让 reverse
return 一个完全 new 链表顺序相反:
function reverse(head) { // Does not modify the given list. Returns a new one.
let node = head;
let reversedHead = null;
while (node) {
reversedHead = new ListNode(node.val, reversedHead);
node = node.next;
}
return reversedHead;
}
我在这里假设 ListNode
构造函数接受第二个参数:
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
我打算把原来的LinkedList反转过来和反转过来的对比一下。如果相同 return 为真。但是,我一直得到错误的结果。我哪里做错了?
var isPalindrome = function(head) {
if(head == null || head.next == null) return true;
let reversedHead = reverse(head)
let count = 0
while (head != null && reversedHead != null) {
if(head.val != reversedHead.val) {
return false
}
head = head.next
reversedHead = reversedHead.next
}
if (head == null && reversedHead == null){
return true
} else {
return false
}
};
var reverse =(head)=> {
let prev = null
let next = new ListNode()
let curr = new ListNode()
curr = head
while(curr){
next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
调用后:
let reversedHead = reverse(head)
您将颠倒列表,即头部变成了尾部,尾部的下一个引用为空。因此你的循环将很快结束,如下所示:
head = head.next
...head
将是 null
.
你需要重新考虑算法。有几种方法可以做到...
而不是 inplace 反转,你可以让 reverse
return 一个完全 new 链表顺序相反:
function reverse(head) { // Does not modify the given list. Returns a new one.
let node = head;
let reversedHead = null;
while (node) {
reversedHead = new ListNode(node.val, reversedHead);
node = node.next;
}
return reversedHead;
}
我在这里假设 ListNode
构造函数接受第二个参数:
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}