OR36 链表的回文结构

OR36 链表的回文结构

较难 通过率：29.47% 时间限制：3秒 空间限制：32M

知识点 链表栈

描述

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

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

测试样例：

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

思路：
1.找中间结点
2.反转链表
3.判断回文结构
1.奇数 while(head != slow)
0.判断值是否相等 1.往后走

1.找中间结点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
}

2.反转逆置后半段链表 此时slow指向中间节点
cur = slow.next;
while(cur != null){
    ListNode curNext = cur.next;
    cur.next = slow;
    slow = cur;
    cur = curNext;
}

//翻转完成
//3. 判断回文
while (head != slow){
    if (slow.val != head.val){
        return false;
    }
    //偶数
    if (head.next == slow){
        return true;
    }
    slow = slow.next;
    head = head.next;
}

偶数个结点图示过程：

完整代码：

public boolean chkPalindrome(ListNode A) {
    // write code here
    //找中间结点
    if(head == null){
        return true;
    }
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //slow走到了中间位置-》翻转
    ListNode cur = slow.next;
    while (cur != null){//当cur为空的时候代表翻转完了
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }


    //翻转完成
    //判断回文
    while (head != slow){
        if (slow.val != head.val){
            return false;
        }
        //偶数
        if (head.next == slow){
            return true;
        }
        slow = slow.next;
        head = head.next;
    }
    return true;
}