Leetcode：回文链表

1、题目描述

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true

示例 2：

输入: head = [1,2]
输出: false

提示：

• 链表 L 的长度范围为 [1, 105]

• 0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2、方法1：使用数组存储链表的值

解题思路

1. 计算链表长度：首先遍历链表，计算链表的长度 len。

2. 存储链表值：创建一个长度为 len 的数组 nums，然后再次遍历链表，将每个节点的值存入数组中。

3. 双指针检查回文：使用双指针法，一个指针 i 从数组头部开始，另一个指针 j 从数组尾部开始，依次比较 nums[i] 和 nums[j] 的值。如果不相等，则链表不是回文链表；如果所有对应值都相等，则是回文链表。

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表两次（计算长度和存储值），以及遍历数组一次。
空间复杂度：O(n)，因为需要使用额外的数组来存储链表的值。

//使用数组来存储链表的值，再通过双指针来判断是否为回文链表public static boolean isPalindrome1(ListNode head){if (head == null || head.next == null) return false;int len =0;ListNode curr = head;while (curr != null){curr = curr.next;len++;}System.out.println(len);int[] nums = new int[len];int t = 0;while (head != null){nums[t++] = head.val;head = head.next;}for (int i = 0,j=len-1; i < len; i++) {if (nums[i] != nums[j]){return false;}j--;}return true;}

3、方法2：快慢指针和反转链表

解题思路

1. 找到链表中点：使用快慢指针法，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针指向链表的中间节点。

   • 如果链表长度为奇数，慢指针指向正中间的节点，此时需要将慢指针移动到中间节点的下一个节点（即后半部分的起点）。

   • 如果链表长度为偶数，慢指针指向前半部分的末尾，直接作为后半部分的起点。

2. 反转后半部分链表：从慢指针指向的节点开始，反转后半部分的链表。

3. 比较前后两部分：将前半部分和反转后的后半部分逐个节点比较值。如果所有对应节点的值都相等，则是回文链表；否则不是。

时间复杂度：O(n)，其中 n 是链表的长度。快慢指针遍历链表一次，反转后半部分链表一次，比较前后两部分一次。
空间复杂度：O(1)，只使用了常数级别的额外空间（快慢指针和反转链表时的临时变量）。

//使用快慢指针和反转链表来实现空间复杂度为O(1)private static boolean isPalindrome2(ListNode head) {ListNode fast=head,slow=head;while (fast!= null && fast.next != null){ //如果链表是奇数，则快指针最后指向不为空,下一个结点才为空，fast.next!= null，如果是偶数链表，则快指针指向为空fast==nullfast = fast.next.next;slow = slow.next;}//如果链表是奇数个结点，把正中的归到左边if (fast != null){slow = slow.next;}slow = reserve(slow);fast = head;while (slow!=null){if (fast.val != slow.val){return false;}fast = fast.next;slow = slow.next;}return true;}//反转链表private static ListNode reserve(ListNode head) {ListNode prev =null;while (head != null){ListNode next = head.next;head.next = prev;prev = head;head = next;}return prev;}