【牛客刷题】每日一练—链表的回文结构

✨hello，进来的小伙伴们，你们好耶！✨

🍖🍖系列专栏：【牛客刷题】

🍈🍈作者简介：一名双非本科大三在读的Java编程小白，启夜星辰，你我同行！

🥟🥟给大家推荐一个超级好用的刷题网站——牛客网！

点击链接注册，开启刷题之路！

问题描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

解题思路

思路： 1.首选判断链表是否为空。

2.找中点：设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。

3.翻转后段链表：设置一个cur引用，让他置于中点的下一个节点cur=slow.next，从cur开始将节点指向逆向翻转，每次翻转完成slow向后走一步slow=cur，让slow走到尾部。

4.分别从链表头尾两端开始比较，如果遇到val值不一样的情况，则不是回文，否则是回文。

5.注意这里我们需要判断偶数的情况，当我们的A.next == slow的时候那么就意味着前后已经遍历完成了，二者即将相遇，如果我们不加判断的话，那么A.next就会继续向下一个节点走，我们的slow也会往后走去，那么两者永远不能相遇，程序就出问题了。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null) {//没有节点
            return false;
        }
        if (A.next == null) { //只有一个节点 一定是回文结构
            return true;
        }
        //找到中点
        ListNode fast = A;
        ListNode slow = A;
        ListNode cur = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //翻转
        cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //比较
        while (A != slow) {
            if (A.val != slow.val) {//有一个不相等说明不是回文结构
                return false;
            }
            if (A.next == slow) {
                /*偶数情况下 A.next等于slow说明二者都遍历完成了,即将相遇,
                那么证明这个结构已经是回文结构了
                如果不加判断那么A继续next,slow继续next会往后走，就会判断错误！*/
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

 运行结果：