题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
function isPail(head) {
if (head === null || head.next === null) {
return true
}
// 3.使用快慢指针
let fast = head,
slow = head,
current = head;
// 遍历链表，移动快慢指针
while (fast.next !== null && fast.next.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// 此时当快指针移动到末端时，慢指针移动到中间，反转慢指针之后的链表
let reverseListHead = reverseList(slow);
// 遍历链表,判断两个链表是否相等
while (current !== null && reverseListHead !== null) {
if (current.val !== reverseListHead.val) {
return false
}
current = current.next;
reverseListHead = reverseListHead.next;
}
return true;
}
//反转链表
function reverseList(current) {
let pre = null,
curr = current;
while (curr != null) {
let nextNode = curr.next;
curr.next = pre;
pre = curr;
curr = nextNode;
}
return pre;
}
module.exports = {
isPail : isPail
};
