# 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

# 方法 1：快慢指针

思路分析：

先找到链表的中间点：

1	2	2	1

找到中间点后我们将其后面的节点进行反转

# 中间节点后面的元素
2	1
# 进行反转
1	2

用反转后的链表跟原始链表进行逐一比较，如果这后半个链表遍历完了大家都相同那么就是回文

# 原始链表
1	2	2	1
# 遍历，后面半个链表进行比较是否相同，相同就是 回文
1	2

如果是如下的链表的话，分析结果：

1	2	3	1

取中间值的后半个链表，然后进行反转

3	1
# 反转
1	3

进行比较，当比较 2 与 3 的时候结果不相同返回 false 不是一个回文链表

1	2	3	1
1	3

如果链表是奇数的情况也是一样的，比如下面的分析结果：

1	2	3	2	1

取中间节点的后半个链表，然后进行反转

3	2	1
# 反转
1	2	3

比较，相同返回 true 是回文链表

1	2	3	2	1
1	2	3

总结：

代码：

	public boolean isPalindrome(ListNode head) {
	ListNode mid = mid(head);
	ListNode reverse = reverse(mid);
	while(reverse != null)
	{
	if(reverse.val != head.val)
	{
	return false;
	}
	reverse = reverse.next;
	head = head.next;
	}
	return true;
	}
	public ListNode mid(ListNode head)
	{
	ListNode p1 = head;
	ListNode p2 = head;
	while(p2 != null && p2.next != null)
	{
	p1 = p1.next;
	p2 = p2.next.next;
	}
	return p1;
	}
	public ListNode reverse(ListNode o1)
	{
	ListNode n1 = null;
	ListNode p = o1;
	while(p != null)
	{
	n1 = new ListNode(p.val, n1);
	p = p.next;
	}
	return n1;
	}

优化后的代码：

	public boolean isPalindrome(ListNode head) {
	ListNode p1 = head; // 慢指针
	ListNode p2 = head; // 快指针
	ListNode n1 = null; // 新链表
	ListNode o1 = head; // 旧链表
	// 快指针停止条件为本身或者 next 为 null
	while(p2 != null && p2.next != null)
	{
	// 慢指针一次走一步
	p1 = p1.next;
	// 快指针一次走两步
	p2 = p2.next.next;
	// 反转链表
	o1.next = n1;
	n1 = o1;
	o1 = p1;
	}
	if(p2 != null) // 奇数，选取后一个节点
	{
	p1 = p1.next;
	}
	while(n1 != null)
	{
	if(n1.val != p1.val)
	{
	return false;
	}
	n1 = n1.next;
	p1 = p1.next;
	}
	return true;
	}