题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
/*
* @Description:
* @Version: 2.0
* @Autor: jinglin.gao
* @Date: 2022-09-14 17:43:42
* @LastEditors: jinglin.gao
* @LastEditTime: 2022-09-15 11:01:08
*/
// 双指针
// 快指针每次走的两个节点的长度
// 慢指针走一个节点的长度
// 在上面的基础上需要判断 链表的长度的的基数和偶数
/****
* 1 2 3 2 1
* 对于基数链表
* 第一步
* slow 1
* fast 3
*
* slow 2
* fast 5
*
* 此时的fast的.next 为null 证明到达链表尾部
*
*
* 1，2，3，4
*
* slow 1
*
*/
// 如果链表长度为奇数
/**
*慢指针一次走一步 快指针一次走两步
*快指针的next为null时 代表快指针走到了节点末尾
此时的慢指针的next 则为奇数链表的中间节点
*/
// 当链表长度为偶数时
function isPail(head) {
if (!head.next) return true;
function ListNode(x) {
this.val = x;
this.next = null;
}
let fast = head;
let slow = head;
// 通过快指针来判断是否到达尾部
while (fast && fast.next) {
// 快指针一次走两步
fast = fast.next.next;
// 慢指针一次走一步
slow = slow.next;
}
// 通过判断 fast是否有值 来进行链表长度 奇偶的判断
// 如果不为null 则代表长度为基数的链表
if (fast) {
// 此时的慢指针的next 刚好指向链表的中间节点
slow = slow.next;
}
// 此时slow代表回文链表的后半段，我们需要将这段链表进行反转 然后再从头跟原始链表进行比较
// 结束条件就是 如果反转后的链表的每一项的值 都跟原始链表的 值相同 则证明 该链表为回文链表
// 演化过程
// 1 2 3 2 1
// 找到后半段链表
// 2 1
// 反转链表
// 1 2
// 用反转后的链表与 原链表做对比
// 反转：1 2
// 原来：1 2 3 2 1
// 2 1
let current = slow;
let reverseNodeList = null;
let newNode = null;
// reverseNodeList = new ListNode(currentNode.val);
while (current) {
// 用原链表的值 创建一个新节点 作为反转链表的上一个节点
newNode = new ListNode(currentNode.val);
if (!reverseNodeList) {
reverseNodeList = newNode;
} else {
newNode.next = reverseNodeList;
}
// 更新反转后链表的长度
reverseNodeList = newNode;
// 原链表长度要减少
current = current.next;
}
// 反转后的链表 与 原链表进行比较
fast = head;
while (reverseNodeList) {
if (reverseNodeList.val != fast.val) return false;
reverseNodeList = reverseNodeList.next;
fast = fast.next;
}
return true;
}
腾讯公司福利 838人发布
投递腾讯等公司6个岗位 >