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
}