Leetcode-234.回文链表

题目描述
请判断一个链表是否为回文链表。

示例 1:

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

输入: 1->2->2->1
输出: true
运行结果

解题思路
第一份代码：先找到中间坐标，再反转后半段链表，再进行比较---利于模板框架
第二份代码：反转前半段代码，但是思路不好想
利用快慢指针和链表倒置的思想
自己做时，只想到了用快慢指针找到中间位置，但是发现没法比较（没有想到将前半段的链表进行倒置）
其他用数组保存或者栈保存数值的方法都不再描述，不太高效
java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //找到链表的中间位置
        ListNode low=head,fast=head;
        while(fast != null && fast.next !=null){
            low=low.next;
            fast=fast.next.next;
        }
        if(fast != null)  low=low.next;
        //将后半段链表反转
        ListNode left=head;
        ListNode right=reverse(low);
        //比较反转后的数值
        while(right != null){
            if(left.val !=right.val){
                return false;
            }
            left=left.next;
            right=right.next;
        }
        return true;

    }
    //从head到结尾反转链表
    public ListNode reverse(ListNode head){
        ListNode pre,cur,nxt;
        pre=null;
        cur=nxt=head;
        while(cur != null){
            nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //找到链表的中间位置
        ListNode start=head;
        ListNode mid=start;
        //利用pre和prepre对前半段进行倒置
        ListNode prepre=null;
        ListNode pre=head;
        while(start != null && start.next != null){
            pre=mid;
            start=start.next.next;
            mid=mid.next;
            pre.next=prepre;
            prepre=pre;
        }
        //证明为奇数个，则mid需要再往右一个（中间的不比较）
        if(start != null) mid=mid.next;

        while(pre != null && mid != null){
            if(pre.val != mid.val){
                return false;
            }
            mid=mid.next;
            pre=pre.next;
        }
        return true;

    }
}