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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

链表 设计 算法 指针

0 人点赞