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
}