回文链表

请判断一个链表是否为回文链表(即从前往后读和从后往前读是一样的)。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean isPalindrome(ListNode head) {
    //没有节点或者只有一个节点
    if(head==null||head.next==null)return true;
    //定义快慢指针，找到中间节点
    ListNode fast=head;
    ListNode slow=head;
    ListNode prev=null;
    while(fast!=null){
        slow=slow.next;
        fast=fast.next==null?fast.next:fast.next.next;
    }
    while (slow!=null){//反转
        ListNode temp = slow.next;
        slow.next = prev;
        prev = slow;
        slow = temp;
    }
    while (head!=null&&prev!=null){//检查
        if (head.val != prev.val){
            return false;
        }
        head = head.next;
        prev = prev.next;
    }
    return true;
}