链表的回文结构

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

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

测试样例：

1->2->2->1

返回：true

什么是回文？：回文是指从前向后读和从后向前读都相同的字符串或数字。例如，“abcba”或数字“121”都是回文。

解决思路:

回文结构，从前向后与从后往前读的值都一样，故我们可以让head和一个尾部元素向中间遍历，遍历期间的值都相等，直到两者相遇，返回true（是回文结构）

1.找到中间节点：

1.通过快慢指针定位中间节点slow:

ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }

2.反转后半节点，从而让尾部元素从后往前遍历:

定义一个节点cur = slow.next;

同时定义一个节点curN来保存cur的下一个节点：

curN = cur.next;(用于下一个节点的反转)

通过cur.next = slow来实现当前节点的反转

slow = cur,更新slow,进入下一个节点

curN = cur； 更新cur节点

直到最后，cur == null,反转成功，此时

3.判断是否为回文结构:

通过while循环(head!=slow)让head节点与slow节点从后往前遍历，如果符合回文节点，遍历过程中  head.val == slow.val;  当遍历到中间时，head == slow 返回true,当然，这种只适合奇数个数的。

换成偶数的，便不能遍历到中间了，此时head.val != slow.val.

怎么解决？

 每次遍历时，判断 head.next == slow，如果这个结果成立，则返回true，是回文列表.

 具体代码如下:

public boolean chkPalindrome(ListNode head) {
        // 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;
        }
        //2.进行翻转
        ListNode cur  = slow.next;
        while(cur!=null)
        {

           ListNode curN = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curN;
        }
        //3.判断回文
        while(head!=slow)
        {
            if(head.val != slow.val)
            {
                return false;
            }
            if(head.next == slow)
            {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }