链表的回文结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表的回文结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1
返回：true

题目链接：链表的回文结构_牛客题霸_牛客网

二、题解

1、先判断链表是否为空或者是否只有一个节点，若是，则返回false：

 if (A == null || A.next == null) {
            return false;
        }

2、若不是，则找链表的中间节点。定义两个节点fast、slow节点，让这两个节点均指向头结点A，让fast节点每次走两步，slow节点每次走一步，当fast节点到达终点的时候，slow节点所指的正是中间结点：

        ListNode fast = A;
        ListNode slow = A;

        //找中间位置
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

3、找到中间结点后，将链表的中间结点以后的部分逆置：

        //翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

4、然后A头结点从前到后遍历，slow节点从后往前遍历，当两节点相遇，则为回文结构。要注意的是，当链表的长度为偶数时，则当A.next = slow时，链表即为回文结构：文章来源地址https://www.toymoban.com/news/detail-737693.html

        //从前到后 从后到前
        while (A != slow) {
            if (A.val != slow.val) {
                return false;
            }
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;

三、完整代码

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return false;
        }
        ListNode fast = A;
        ListNode slow = A;

        //找中间位置
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //翻转
        ListNode 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) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

到了这里，关于链表的回文结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！