题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

 

输入：head = [1,2,2,1]
输出：true

示例 2：

 

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

 

解题思路

1.首先我们利用快慢指针找到链表的中间节点，详细方法请参考【876.链表的中间节点】
2.然后我们将链表的后半部分反转，详细方法请参考【206.反转链表】

3.最后我们对原来的链表（head）和反转后的后半部分链表（reverse）从头开始遍历，结束条件为（reverse == null），在遍历的过程中，我们比较两个链表中的值，若遍历到reverse==null，两个链表中的值都相等，则说明原链表前半部分与反转后的后半部分链表相同，此链表为回文链表。

代码实现

class Solution {
    public boolean isPalindrome(ListNode head) {
      if(head == null || head.next == null){
            return true;
        }  
        ListNode mid = mid(head);
        ListNode reverse = reverse(mid);

        while(reverse != null){
            if(reverse.val != head.val){
                return false;
            }else{
                reverse = reverse.next;
                head = head.next;
            }
        }
         return true;
        


    }
    private ListNode reverse(ListNode head){
        ListNode per = null;
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = per;
            per = cur;
            cur = curNext;
    }
             return per;
    }
    private ListNode mid(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    }

测试结果