234. Palindrome Linked List
Easy
Given the
head of a singly linked list, return true if it is a palindrome or false otherwise.Example 1:
Input: head = [1,2,2,1]
Output:
true
Example 2:
Input: head = [1,2]
Output:
false
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 0 <= Node.val <= 9
Follow up: Could you do it in
O(n) time and O(1) space?
把中點以前的值都記錄起來，接著再進行比對。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head==nil || head.Next==nil { return true }
arr := make([]int, 0)
pre, fast := head, head
for fast!=nil && fast.Next!=nil {
arr = append(arr, pre.Val)
fast = fast.Next.Next
pre = pre.Next
}
if pre.Val!= arr[len(arr)-1] {
pre = pre.Next
}
for pre!= nil {
if pre.Val==arr[len(arr)-1] {
arr = arr[:len(arr)-1]
}
pre = pre.Next
}
if len(arr)==0 {
return true
}
return false
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
p1, p2 := head, head
for p2.Next != nil && p2.Next.Next != nil {
p1 = p1.Next
p2 = p2.Next.Next
}
var front *ListNode
mid, end := p1.Next, p1.Next
p1.Next = nil
p1 = mid
for mid != nil {
end = mid.Next
mid.Next = front
front, mid = mid, end
}
for front != nil {
if head.Val != front.Val {
return false
}
head = head.Next
front = front.Next
}
return true
}