一.解法

https://leetcode-cn.com/problems/palindrome-linked-list/
要点：快慢指针，翻转链表
Python因为切片方便，采用了回文链表转换回文数组然后对数组切片比较的方法，用了额外的数组空间。
C++和Java用了快慢指针找中点，然后将中点后的链表翻转，原中点的next变为null，最后比较前后两个链表是否完全相同。

二.Python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        answer=[]
        temp=head;
        while temp!=None:
            answer.append(temp.val)
            temp=temp.next
        return answer==answer[::-1]

三.C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fast,* slow;
        if(!head||!head->next) return true;
        
        fast=head;slow=head;
        while(fast){
            fast=fast->next;
            if(!fast) break;
            fast=fast->next;
            slow=slow->next;
        }
        
        ListNode* mid=slow;
        
        ListNode*pre,*nex;
        pre=NULL;
        while(mid){nex=mid->next;
                   mid->next=pre;
                   pre=mid;
                   mid=nex;
        }
        
        
        while(head&&pre){
            
            
            if(head->val!=pre->val) return false;
            
            head=head->next;
            pre=pre->next;
            
        }
        
        return true;
    }
};

四.java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public static boolean isPalindrome(ListNode head) {
        //找到中点位置，从这里开始反转后半段链表
        //再次找到中点位置，中点与head开始进行对比，中途有不相同的返回false，否则最后返回true
        ListNode guard = new ListNode(-1);
        guard.next = head;
        ListNode slow = guard;//遍历结束时slow指向的是mid的前一个
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode head2 = reverse(slow.next);
        slow.next = null;

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

    private static ListNode reverse(ListNode head){
        if(head == null)
            return null;
        ListNode guard = new ListNode(0);
        guard.next = head;
        ListNode pre = guard;
        ListNode cur = pre.next;
        while (cur.next != null){
            ListNode nex = cur.next;

            cur.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
        }
        return pre.next;
    }
}