234. 回文链表

题目描述：

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 10^5] 内
• 0 <= Node.val <= 9

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

---

解题分析及思路：

方法一：数组模拟

我们可以使用数组存储链表的值，然后遍历数组判断它是否是一个回文数组。

func isPalindrome(head *ListNode) bool {
	var nums = make([]int, 0)
	for head != nil {
		nums = append(nums, head.Val)
		head = head.Next
	}
	for i := 0; i < len(nums)/2; i++ {
		if nums[i] != nums[len(nums)-1-i] {
			return false
		}
	}
	return true
}

复杂度：

• 时间复杂度：O(N)，其中 N 是链表的节点数量。
• 空间复杂度：O(N)，其中 N 是链表的节点数量。

执行结果：

• 执行耗时:129 ms,击败了26.16% 的Go用户
• 内存消耗:11.1 MB,击败了46.24% 的Go用户

方法二：栈

可以使用栈的特性，先遍历链表将前一半的元素入栈，然后再遍历链表的后一半，同时出栈并比较。

如何判断链表的后一半呢？

• 可以使用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表尾部时，慢指针刚好走到链表的中间。
• 也可以先遍历链表获取链表的长度，然后再遍历链表的前一半入栈，再遍历链表的后一半出栈并比较。

func isPalindrome(head *ListNode) bool {
	var l int
	var node = head
	for node != nil {
		l++
		node = node.Next
	}
	var stack = make([]int, 0)
	for i := 0; i < l/2; i++ {
		stack = append(stack, head.Val)
		head = head.Next
	}
	if l%2 == 1 {
		head = head.Next
	}
	for i := 0; i < l/2; i++ {
		if stack[len(stack)-1] != head.Val {
			return false
		}
		stack = stack[:len(stack)-1]
		head = head.Next
	}
	return true
}

复杂度：

• 时间复杂度：O(N)，其中 N 是链表的节点数量。
• 空间复杂度：O(N)，其中 N 是链表的节点数量。

执行结果：

• 执行耗时:120 ms,击败了52.02% 的Go用户
• 内存消耗:12.6 MB,击败了32.33% 的Go用户