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

ゝ一纸荒年。 2022-12-18 03:57 122阅读 0赞

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

//测试样例：
    //1->2->2->1
    //返回：true

public boolean chkPalindrome() {
        
            // write code here
            ListNode fast = this.head;
            ListNode slow = this.head;
    
            if (this.head == null){
        
                return false;
            }
            if (this.head.next == null){
        
                //只有头节点自己，必然是回文
                return true;
            }
            //找到中间
            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.next;
            }
            //此时slow是最后一个了
            while (slow != this.head){
        
                if (this.head.val != slow.val){
        
                    return false;
                }
                 if (this.head.next == slow){
        
                    return true;
                }
                slow = slow.next;
                this.head = this.head.next;
            }
            return true;
        }