【日拱一卒】链表——回文判断

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	
	fast := head
	slow := head

	// 快慢指针，快指针每次移动两步，慢指针每次移动一步
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	//如果是奇数，则慢指针再移动一步，到达中心点
	if fast != nil {
		slow = slow.Next
	}

	// 慢指针反转
	var pre *ListNode = nil
	for slow != nil {
		pre, slow, slow.Next =slow, slow.Next, pre
	}

	cur := head
	for cur != nil && pre != nil {
		if cur.Val == pre.Val {
			cur = cur.Next
			pre = pre.Next
		} else {
			return false
		}
	}

	return true
}