【算法面试必刷Java版十三】判断一个链表是否为回文结构

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：判断一个链表是否为回文结构

描述：

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0^50≤n≤105，链表中每个节点的值满足 |val|≤107

思路：反转链表

额外需要注意的一个点是，链表需要复制一份，否则无法对比。

1. 复制链表。
2. 反转链表。
3. 对比链表。

代码：

public boolean isPail(ListNode head) {
    // 复制链表
    ListNode cur = head;
    ListNode copy = new ListNode(-1);
    ListNode copyCur = copy;
    while (cur != null) {
        copyCur.next = new ListNode(cur.val);
        cur = cur.next;
        copyCur = copyCur.next;
    }
    // 反转链表
    ListNode reverse = reverse(copy.next);
    // 对比链表
    cur = head;
    while (cur != null && reverse != null) {
        if (cur.val != reverse.val) {
            return false;
        }
        cur = cur.next;
        reverse = reverse.next;
    }
    if (cur == null && reverse == null){
        return true;
    }else {
        return false;
    }
}

public ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    ListNode next;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101