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

✨专栏：《Java SE语法》 | 《数据结构与算法》 | 《C生万物》

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️

🙏小杨水平有限，欢迎各位大佬指点，相互学习进步！

文章目录

• 1. 题目描述
• • 测试样例：
  • 2. 思路
  • 3. 代码

    1. 题目描述

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

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

    测试样例：

    输入：1->2->2->1

    输出：true

    题目链接🔗

    2. 思路

    1. 判断链表是否为空，如果为空，那么链表就是回文的

    2. 找到中间元素

       1. 定义两个指针slow和fast，fast每次移动两步，slow每次移动一步，当fast走到链表中的最后一个节点是，slow就指向了链表的中间节点。

       

    3. 反转链表后半部分的元素

       1. 定义指针cur指向中间节点的next
       2. 从中间节点循环遍历链表
       3. 定义指针curNext指向cur的next（保存下一个节点）
       4. 将当前节点的next指向slow
       5. slow移动到当前节点的cur位置
       6. cur移动到下一个节点

       

    4. 同时遍历反转后的链表和原始链表的前半部分，并比较每个节点的值。如果所有的节点都匹配，那么链表就是回文；否则它不是回文。

       1. 一个从前一个从后循环遍历链表，直到相遇
       2. 判断两个当前节点是否相同，如果不同返回false
       3. 如果相同判断head的next等不等于slow，如果等于直接返回true（链表节点个数为偶数个）
       4. head移动到下一个节点
       5. slow移动到下一个节点

       

    3. 代码

    import java.util.*;
    /*
    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class PalindromeList {
        public boolean chkPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }
            // write code here
            // 1.找到中间元素
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            // 2.反转链表
            ListNode cur = slow.next;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            // 3.一个向后遍历一个向前遍历
            while (slow != head) {
                if (slow.val != head.val) {
                    return false;
                }
                if (head.next == slow) {
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
        }
    }
    

    运行结果：