蓝桥与力扣刷题（234 回文链表）

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

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

解题思路＋代码：

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        /**
        思路：
        1.判断链表是否为空或者单节点链表，为空直接返回true
        2.添加快慢指针，快指针一次走2步，慢指针一次走1步，即快指针的速度是慢指针的2倍（此时当快指针遍历到链表的最后，慢指针遍历到链表的中间）
        3.反转后半部分链表，与前半部分链表逐一匹配，一一对应返回true，否则返回false
        */
        if (head == null || head.next == null){
            return true;
        }
        
        // 声明快慢指针
        ListNode fastNode = head;
        ListNode slowNode = head;
        
        // 遍历链表，慢指针找到链表中点
        while(fastNode != null && fastNode.next != null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        
        //反转慢指针后半部分链表与前半部分链表逐一匹配
        ListNode resversHalfList  = resversList(slowNode);
        
        ListNode P1 = head;
        ListNode p2 = resversHalfList;
        
        boolean res = true;
        
        while(p2 != null){
            if(P1.val != p2.val){
                res = false;
                break;
            }
            P1 = P1.next;
            p2 = p2.next;
        }
        
        // resversList(resversHalfList);
        
        return res;
    }
    
    private ListNode resversList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode nextTemp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }
    
}

总结：（错误思路：写这道题时我最初的思路是找到中间最大的数，然后依次向左右两边逐一遍历判断是否对称相等，一一对应为true，否则为false。）没错，上面的思路有很大的问题，且时间空间复杂度会相对复杂，因此我使用AI查询了我解题思路的错误所在。一：在回文链表当中，最大的数可能不止一个，此时的回文链表在找到最大的中间数依次向左右两侧依次遍历也可能会得到与预期相反的结果；二：通过指针向左右依次遍历判断不如快慢指针（上述代码有相应的解释如何找到链表的中点）找到中点后将前（后）链表部分反转，首先可判断前后部分的长度是否相等，不相等直接返回false，长度相等时则继续逐一匹配，直到确定是回文链表时返回true，使用快慢指针来遍历链表的时间和空间复杂度相对而言较简单，耗时较短。