深色模式
BM13 判断一个链表是否为回文结构
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0 \le n \le 10^50≤n≤105，链表中每个节点的值满足 |val| \le 10^7∣val∣≤107
示例1
输入：{1}
返回值：true
示例2
输入：{2,1}
返回值：false
说明：2->1
示例3
输入：{1,2,2,1}
返回值：true 说明：1->2->2->1
ts
/*class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类 the head
* @return bool布尔型
*/
export function isPail(head: ListNode): boolean {
// write code here
var stack = [];
if(!head) return false;
var p = head;
while(p) {
stack.push(p);
p = p.next;
}
var node;
while(head) {
node = stack.pop();
if(head.val !== node.val) return false;
head = head.next;
}
return true;
}方法二
方法一的空间复杂度为，较大，可以使用快慢指针，快指针的速度为慢指针的两倍，当快指针到达链表尾部时，慢指针到达中间位置，将慢指针之后的部分进行反转，再与前半部分进行比较。
具体步骤
- 如图：
- 时间复杂度： O(N)，遍历链表
- 空间复杂度：O(1)，常数级空间复杂度
ts
/*class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类 the head
* @return bool布尔型
*/
export function isPail(head: ListNode): boolean {
// write code here
if(!head) return false;
var fast = head;
var slow = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 链表长度奇数
if(fast) slow = slow.next;
slow = reverse(slow)
fast = head;
while(slow) {
if(slow.val !== fast.val) return false;
slow = slow.next;
fast = fast.next;
}
return true;
}
function reverse(head: ListNode) : ListNode{
var prev = null;
while (head) {
var next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}