LeetCode 234. 回文链表(Golang)_golang148回文链表

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

示例 1:

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

示例 2:

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

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

思路：遍历链表，将所有节点按顺序存储到map集合中，通过map的键从两头开始遍历对比，值不相等返回false。

func isPalindrome(head *ListNode) bool {
	m := make(map[int]*ListNode)
	i := 0
	m = TraverListNode(head, m, i)
	start := 0
	end := len(m) - 1
	for start <= end {
		if m[start].Val != m[end].Val {
			return false
		}
		start++
		end--
	}
	return true
}

func TraverListNode(head *ListNode, m map[int]*ListNode, i int) map[int]*ListNode {
	if head == nil {
		return m
	}
	m[i] = head
	i++
	return TraverListNode(head.Next, m, i)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24