## 题目 #

Given a singly linked list, determine if it is a palindrome.

Example 1:

``````
Input: 1->2
Output: false

``````

Example 2:

``````
Input: 1->2->2->1
Output: true

``````

Could you do it in O(n) time and O(1) space?

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/leetcode-go/structures"
)

// ListNode define
type ListNode = structures.ListNode

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

// 解法一
slice := []int{}
}
for i, j := 0, len(slice)-1; i < j; {
if slice[i] != slice[j] {
return false
}
i++
j--
}
return true
}

// 解法二
// 此题和 143 题 Reorder List 思路基本一致
return true
}
res := true
// 寻找中间结点
for p2.Next != nil && p2.Next.Next != nil {
p1 = p1.Next
p2 = p2.Next.Next
}
// 反转链表后半部分  1->2->3->4->5->6 to 1->2->3->6->5->4
preMiddle := p1
preCurrent := p1.Next
for preCurrent.Next != nil {
current := preCurrent.Next
preCurrent.Next = current.Next
current.Next = preMiddle.Next
preMiddle.Next = current
}
// 扫描表，判断是否是回文
p2 = preMiddle.Next
// fmt.Printf("p1 = %v p2 = %v preMiddle = %v head = %v\n", p1.Val, p2.Val, preMiddle.Val, L2ss(head))
for p1 != preMiddle {
// fmt.Printf("*****p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
if p1.Val == p2.Val {
p1 = p1.Next
p2 = p2.Next
// fmt.Printf("-------p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
} else {
res = false
break
}
}
if p1 == preMiddle {
if p2 != nil && p1.Val != p2.Val {
return false
}
}
return res
}

// L2ss define