回文列表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：

回文链表和回文字符串类似，反转列表后和原链表值一一对应，所以首先能想到的解法是复制一个链表，然后问题转化为 反转链表，这样的空间复杂度是 $O(n)$。

题目进阶要求用 $O(1)$ 的空间复杂度。考虑不复制原链表的方案，回文的另一个特点是中心对称，所以问题转化为怎么找到链表的中心位置，这里可以用到双指针技巧，定义slow 和flow，slow 以步长 1 前进，fast以步长 2 前进，当 fast.Next = nil 时，slow的位置就是链表中心位置。当然还需要考虑链表个数奇偶数的情况。然后从中心位置反转后半部分链表与前半部分比较。

代码：

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	var cp = Copy(head)
	rcp := reverseList2(cp)
	for ;head.Next != nil && rcp.Next != nil; {
		if head.Val != rcp.Val {
			return false
		} else {
			head = head.Next
			rcp = rcp.Next
		}
	}
	return true
}

func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	last := reverseList2(head.Next)
	head.Next.Next = head
	head.Next = nil
	return last
}

func Copy(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var result = &ListNode{}
	result.Val = head.Val
	result.Next = Copy(head.Next)
	return result
}