目录

题目链接：牛客网OR36.链表的回文结构

一.题目要求

二.解题思路

三.具体代码

题目链接：牛客网OR36.链表的回文结构

一.题目要求

描述：

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

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

测试样例：

1->2->2->1

返回：true

二.解题思路

        我们看到该题可以想到的就是 "对折" 该链表，然后一对一对比结点元素是否相等。

        那么问题来了，如何实现 "对折" 该链表呢？

        我们可以先找到元素的中间结点，然后逆置后半部分的链表，最后和前半部分的链表进行 "结点-结点" 一一对应比较，元素值全部相等即为回文结构。

求元素的中间结点：先求出链表总长度从而求得一半的长度，通过对链表循环遍历即可找到中间结点。

详细可以点击：求元素的中间结点

链表的逆置：可以通过迭代，利用栈结构，使用递归等方法实现链表的逆置。

详细可以点击：链表的逆置

三.具体代码

public class PalindromeList {
    private int midsizeOf(ListNode A){
        ListNode cur=A;
        int size=0;
        while(cur!=null){
            size++;
            cur=cur.next;
        }
        return size/2;
    }

    private ListNode reserve(ListNode A){
        ListNode cur=A;
        ListNode prev=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }

    public boolean chkPalindrome(ListNode A) {
        // write code here
        int midsize=midsizeOf(A);
        ListNode rhead=A;
        for(int i=0;i<midsize;i++){
            rhead=rhead.next;
        }
        rhead=reserve(rhead);

        while(A!=null&&rhead!=null){
            if(A.val!=rhead.val){
                return false;
            }
            A=A.next;
            rhead=rhead.next;
        }

        return true;

    }
}

如想了解链表（LinkedList）相关知识，请查阅：

LinkedList（链表）的介绍及自我实现

如有建议或想法，欢迎一起讨论学习~