双指针，一个往后读一个往前读，如果不一样就false，否则就是回文链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
var cur *ListNode = head
var arr []int = []int{}
for cur != nil {
arr = append(arr,cur.Val)
cur = cur.Next
}
start := 0
end := len(arr) - 1
for start < end {
if arr[start] != arr[end] {
return false
}
start++
end--
}
return true
}
或者copy一个链表，把它反转了，和原来的链表一个一个比较，如果反转后的和原来的一样就是回文链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var reversedHead *ListNode = nil
for head != nil {
// 保存下一个节点
next := head.Next
// 将当前节点插入到反转链表的头部
head.Next = reversedHead
reversedHead = head
// 移动到下一个节点
head = next
}
return reversedHead
}
func copyList(head *ListNode) *ListNode {
if head == nil {
return nil
}
newHead := &ListNode{Val: head.Val}
cur := newHead
for head.Next != nil {
head = head.Next
cur.Next = &ListNode{Val: head.Val}
cur = cur.Next
}
return newHead
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
copiedHead := copyList(head)
reversedHead := reverseList(copiedHead)
// 比较原链表和反转后的链表
p1, p2 := head, reversedHead
for p1 != nil && p2 != nil {
if p1.Val != p2.Val {
return false
}
p1 = p1.Next
p2 = p2.Next
}
return true
}