# 判断链表的回文结构
给定一个单链表的头节点head， 请判断该链表是否为回文结构。
- 使用容器方法特别简单（可是使用数组或者栈）
- 改原链表的方法就需要注意边界了
# 代码实现
package link_list
/*
力扣原题：LCR 027. 回文链表
链接： https://leetcode.cn/problems/aMhZSa/
*/
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
if head == nil {
return true
}
// 找到前中点
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
preMid := slow
// 对中点后续的节点反转链表
var pre, next *ListNode = nil, preMid
for next != nil {
tem := next.Next
next.Next = pre
pre = next
next = tem
}
// 校验是否是回文链表
p1, p2 := head, pre
ans := true
for p1 != nil && p2 != nil {
if p1.Val != p2.Val {
ans = false
break
}
p1 = p1.Next
p2 = p2.Next
}
// 还原链表
pre, next = nil, pre
for next != nil {
tem := next.Next
next.Next = pre
pre = next
next = tem
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 其他拓展
# 方法论
- 对于写题，不用太在乎空间复杂度，一切为了时间复杂度
- 对于口述，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
# 常用数据结构与技巧
- 使用容器(哈希表、数组等)
- 快慢指针
# 快慢指针练习
- 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
- 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个