LeetCode-Day22 (C#) 234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

解题思路：
快慢指针找中点，将链表一分为二（偶数个节点时等分，奇数个节点时前半部分多一个节点），然后用 206 题的反转链表的方法把后半部分链表反转一下，最后顺序比较两个小链表是否每个元素相等就 OK 啦。

public class Solution {
    public bool IsPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;

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

        ListNode pre = null;
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        //从链表的两端开始比较，奇数节点时中间节点就可以忽略了
        while(pre!=null){
            if(pre.val != head.val) return false;
            head = head.next;
            pre = pre.next;
        }
        return true;
    }
}