LCR 027. 回文链表 不利用额外空间实现快慢指针

LCR 027. 回文链表

给定一个链表的 头节点 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) 空间复杂度解决此题？

注意：本题与主站 234 题相同：. - 力扣（LeetCode）

快慢指针

35min

1.定义快指针使得快指针到终点后慢指针刚好到中点 快指针前进两步 慢指针前进一步

        此时需要注意可以把快慢指针定义到同一起点方便管理

2.将中点后的链表逆序 得到后半部分

3.逆序的头结点z->a 与 a->z比较。如果有一个不同则不为回文数

    public boolean isPalindrome(ListNode head) {//方法2 快慢指针ListNode fastPoint = head;ListNode slowPoint = head;//1.定义快指针使得快指针到终点后慢指针刚好到中点 快指针前进两步 慢指针前进一步while(fastPoint != null && fastPoint.next != null){fastPoint = fastPoint.next.next;slowPoint = slowPoint.next;}//*此时的慢指针为中点//2.将中点后的链表逆序ListNode prev = null;ListNode curr = slowPoint;ListNode nextTemp = null;while (curr != null) {nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}fastPoint = head;//prev为翻转的链表while(prev != null){if(prev.val != fastPoint.val){return false;}prev = prev.next;fastPoint = fastPoint.next;}return true;//3.逆序后的链表与开始的头节点相比较//4.将逆序的链表重新逆序得到head}