原题：leetcode-234
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /* 为什么把整条链表反转不可行，因为整条反转的时候，原链表也也跟着改变了，永远返回true 正确的思路： 1.找到中间位置； 2.把后半部分反转 3.两段链表从头开始一一比较 */ class Solution { public boolean isPalindrome(ListNode head) { if(head==null||head.next==null)return true; //1.先找到中间位置:用快慢指针法 ListNode start=head; ListNode low=head; ListNode fast=head; while(fast.next!=null&&fast.next.next!=null){ fast=fast.next.next; low=low.next; } low=low.next; //2.把后半段的链表反转 ListNode reverse=reverseLinkList(low); // 3.两段链表从头开始一一比较 while(low!=null&&reverse!=null){ if(start.val!=reverse.val){ return false; } reverse=reverse.next; start=start.next; } return true; } public ListNode reverseLinkList(ListNode head){ ListNode cur=null; ListNode pre=head; while(pre!=null){ ListNode last=pre.next; pre.next=cur; cur=pre; pre=last; } return cur; } }