题目描述
给定一个链表，请判断该链表是否为回文结构。
示例1
输入
[1,2,2,1]
返回值
true
思路:
双指针，快指针一次走两步，慢指针一次走一步，快指针走完，慢指针走到中点。然后将中点开始后面节点逆序，比较完之后再将还原该链表。
例如：1->3->5->3->1，慢指针会到达5处，然后右半部分逆序，将5的next指向null，将后面3的next指向5，将1的next指向3，得到1->3->5<3<1，一个节点从head开始遍历，一个节点从尾节点开始遍历，比较，一直到中点位置停，若相同，则为true，否则为false。
public class IsPailMe {public static void main(String[] args) {}/**** @param head ListNode类 the head* @return bool布尔型*/public boolean isPail (ListNode head) {if(null == head){return false;}ListNode fast = head;ListNode slow = head;while(null != fast && fast.next != null){slow = slow.next;fast = fast.next.next;}// 1 2 3 2 1// 从slow出开始逆序链表后面的节点ListNode tempHead = new ListNode();ListNode temp = slow;// 逆序链表while(null != temp){temp = slow.next;slow.next = tempHead.next;tempHead.next = slow;slow = temp;}ListNode first = head;tempHead = tempHead.next;while(null != first && tempHead != null && first.val == tempHead.val){first = first.next;tempHead = tempHead.next;}if(null == tempHead){return true;}return false;}}class ListNode {int val;ListNode next = null;ListNode() {}ListNode(int val) {this.val = val;}}
