LeetCode 234. 回文链表-蒲公英云

LeetCode 234. 回文链表

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true

解题思路：
1.快慢指针找到中点
2.将链表分为左右两个链表
3.将右边的链表逆序
4.对比左右链表是否相等（右边链表长度可能比左边链表少1 因此右边链表为空时结束循环）

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)
            return true;
        ListNode p1 = head;
        ListNode p2 = head.next;
        while (p2!=null) {
            p2 = p2.next;
            if (p2 == null)
                break;
            p2 = p2.next;
            p1 = p1.next;
        }
        //奇数，则p1指向中点
        //偶数，则p1指向左边的最后一个节点
        p2 = p1.next;
        p1.next = null;
        //p2逆序
        ListNode newHead = null;
        while(p2!=null){
            ListNode p = p2.next;//保存链表的next
            p2.next = newHead;//将head的next指向新的链表头
            newHead = p2;//将新链表头指向头结点
            p2 = p;//将head赋给之前保存的next
        }
        //head 为左边链表 newhead为右边链表
        while (newHead!=null){
            if(head.val!=newHead.val)
                return false;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
}