234. 回文链表 (opens new window)

1.反转链表

解题思路：遍历两次链表：第一次遍历将链表后半部分进行原地反转（一种做法是使用头插法头尾逆置；另一种改变后边段链表节点的next指向）；第二次遍历用头尾双指针同时向中间靠拢，判断回文链表。

时间O(n)，空间O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next==null) return true;
        if(head.next!=null&&head.next.next==null){
            if(head.val!=head.next.val) return false;
            return true;
        }
        //找到中间位置
        int step=0;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
            if(fast.next==null){
                step++;
                break;
            }
            fast=fast.next;
            step++;
            if(fast.next==null){
                break;
            }
        }
        //原地逆置
        ListNode pre=slow;
        ListNode curr=slow.next;
        while(curr.next!=null){
            ListNode next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        curr.next=pre;
        ListNode tail=curr;
        for(int i=0;i<step;i++){
            if(tail.val!=head.val) return false;
            tail=tail.next;
            head=head.next;
        }
        return true;
    }
}

2.开辟空间

另一种做法开辟一个数组空间，保存链表的值。然后在数组上遍历判断是否回文。

3.递归

在递归函数外部使用一个指针变量保存头结点，每次头节点和当前节点(尾节点)比较过后，改变头结点指针。同时利用递归的特性，将当前节点回退到前驱节点进行判断，具体流程如下：

• next指针不为空，则递归搜索p.next节点，curr=p.next
• 当前节点curr和头结点进行比较
• 头节点向后移动head=head.next
• 退出当前循环后，当前节点curr指向的就是p节点的前驱，重复步骤二