爱敲代码的小杨.

爱敲代码的小杨.

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

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

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

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

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

1. 题目描述

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

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

测试样例:

题目链接🔗

2. 思路

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

  2. 找到中间元素

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

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

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

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

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

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

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

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

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;
    }
}

运行结果: 【每日一题】牛客网——链表的回文结构-LMLPHP
【每日一题】牛客网——链表的回文结构-LMLPHP

02-14 09:25